milkway: add a base32 implementation

2 files changed, 215 insertions, 10 deletions

diff --git a/lib/base32.c b/lib/base32.c
index 097ecc6..e52a9da 100644
--- a/lib/base32.c
+++ b/lib/base32.c
@@ -12,18 +12,217 @@
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Library General Public License for more
  */
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+/* License
+ * -------
+ *
+ * The UIA source code is distributed under the MIT open source license,
+ * with the exception of the following components, which are distributed
+ * under alternate licenses due to dependencies on existing code used
+ * in those components:
+ * 1. The graphical control application in the 'uianet/ctl' subdirectory
+ *  is distributed under the GNU General Public License (GPL),
+ *  because it relies on the GPL-licensed Qt toolkit from Trolltech.
+ *
+ * 2. The netsteria application in the 'netsteria' subdirectory
+ *   is distributed under the GNU General Public License (GPL),
+ *  because it relies on the GPL-licensed Qt toolkit from Trolltech.
+ *
+ * 3. The SST protocol implementation in the 'sst' subdirectory
+ *  is distributed under the GNU General Public License (GPL),
+ *  because it relies on the GPL-licensed Qt toolkit from Trolltech.
+ *
+ * 4. PLY (Python Lex-Yacc), included in uianet/naming/rpcgen/ply,
+ *  is distributed under the GNU Lesser General Public License (LGPL).
+ *  PLY is used only for compiling uianet -- it is not needed to run
+ *  UIA programs.
+ */
+
 #include "base32.h"
 
+#include <string.h>
+
+// Decoding table for our base32 encoding scheme
+static const signed char dectab[256] = {
+    -1, -1, -1, -1, -1, -1, -1, -1,		// Control chars
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,		// Space-"'"
+    -1, -1, -1, -1, -1, -1, -1, -1,		// '('-'/'
+    0,  1,  2,  3,  4,  5,  6,  7,		// 0-7
+    8,  9, -1, -1, -1, -1, -1, -1,		// 8-'?'
+    -1, 10, 11, 12, 13, 14, 15, 16,		// '@', A-G
+    17,  1, 18, 19,  1, 20, 21,  0,		// H-O: I,L = 1, O = 0
+    22, 23, 24, 25, 26, 27, 28, 29,		// P-W
+    30, 31,  2, -1, -1, -1, -1, -1,		// X-'_': Z = 2
+    -1, 10, 11, 12, 13, 14, 15, 16,		// '@', a-g
+    17,  1, 18, 19,  1, 20, 21,  0,		// h-o: i,l = 1, o = 0
+    22, 23, 24, 25, 26, 27, 28, 29,		// p-w
+    30, 31,  2, -1, -1, -1, -1, -1,		// x-DEL: z = 2
+
+    -1, -1, -1, -1, -1, -1, -1, -1,		// Latin-1 ...
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+};
+
+size_t
+mw_base32_encode_length(size_t len)
+{
+    return ((len * 8) / 5) + ((len % 5) != 0) + 1;
+}
+
+size_t
+mw_base32_decode_length(size_t len)
+{
+    return ((len * 5) / 8);
+}
+
 int
-mw_base32_encode(void *in, size_t inlen,
-		 void *out, size_t *outlen)
+mw_base32_encode(const void *buf, size_t size,
+		 char *out_str, size_t outlen)
 {
-    return 0;
+    static const char conv[32] = "0123456789ABCDEFGHJKMNPQRSTUVWXY";
+
+    // Handle complete 40-bit groups
+    const mw_uint8_t *b = (const mw_uint8_t*)buf;
+    char *s = out_str;
+    int i = 0;
+    mw_uint32_t bhi;
+
+    if (mw_base32_encode_length(size) > size)
+	return MW_TOO_SMALL;
+
+    while (i + 5 <= size) {
+	mw_uint32_t bhi = ((mw_uint32_t)b[i] << (32 - 24)) |
+	    ((mw_uint32_t)b[i + 1] << (24 - 24));
+	mw_uint32_t blo = (bhi << 24) |
+	    ((mw_uint32_t)b[i + 2] << 16) |
+	    ((mw_uint32_t)b[i + 3] << 8) |
+	    ((mw_uint32_t)b[i + 4] << 0);
+
+	s[0] = conv[(bhi >> (35-24)) & 0x1f];
+	s[1] = conv[(bhi >> (30-24)) & 0x1f];
+	s[2] = conv[(blo >> 25) & 0x1f];
+	s[3] = conv[(blo >> 20) & 0x1f];
+	s[4] = conv[(blo >> 15) & 0x1f];
+	s[5] = conv[(blo >> 10) & 0x1f];
+	s[6] = conv[(blo >> 5) & 0x1f];
+	s[7] = conv[(blo >> 0) & 0x1f];
+	i += 5;
+	s += 8;
+    }
+
+    // Handle the final partial group
+    bhi = (mw_uint32_t)b[i++] << (32 - 24);
+    s[2] = 0;
+    if (i < size) {
+	bhi |= (mw_uint32_t)b[i++] << (24 - 24);
+	mw_uint32_t blo = bhi << 24;
+	s[4] = 0;
+	if (i < size) {
+	    blo |= (mw_uint32_t)b[i++] << 16;
+	    s[5] = 0;
+	    if (i < size) {
+		blo |= (mw_uint32_t)b[i++] << 8;
+		s[7] = 0;
+		if (i < size) {
+		    blo |= (mw_uint32_t)b[i++] << 0;
+		    s[8] = 0;
+		    s[7] = conv[(blo >> 0) & 0x1f];
+		}
+		s[5] = conv[(blo >> 10) & 0x1f];
+		s[6] = conv[(blo >> 5) & 0x1f];
+	    }
+	    s[4] = conv[(blo >> 15) & 0x1f];
+	}
+	s[2] = conv[(blo >> 25) & 0x1f];
+	s[3] = conv[(blo >> 20) & 0x1f];
+    }
+    s[0] = conv[(bhi >> (35 - 24)) & 0x1f];
+    s[1] = conv[(bhi >> (30 - 24)) & 0x1f];
+
+    return strlen(out_str);
 }
 
 int
-mw_base32_decode(void *in, size_t inlen,
-		 void *out, size_t outlen)
+mw_base32_decode(const char *str, size_t inlen,
+		 void *out_buf, size_t *out_size)
 {
-    return 0;
+    const char *s = str;
+    const char *smax = s + inlen;
+    mw_uint8_t *b = (mw_uint8_t*)out_buf;
+    mw_uint8_t *bmax = b + *out_size;
+
+#define DECODE(c)				\
+    c = *s++;					\
+    while (c == '-')				\
+	c = *s++;				\
+    if (s >= smax)				\
+	return MW_TOO_BIG;			\
+    c = dectab[(mw_uint8_t)c];			\
+    if (c < 0)					\
+	break;
+
+#define OUTPUT(v)				\
+    if (b == bmax)				\
+	return MW_TOO_SMALL;			\
+    *b++ = (v);
+
+    while (1) {
+	signed char c;
+	mw_uint32_t bhi, blo;
+
+	// Decode first binary output byte in a 40-bit group
+	DECODE(c);
+	bhi = (mw_uint32_t)c << (35 - 24);
+	DECODE(c);
+	bhi |= (mw_uint32_t)c << (30-24);
+	OUTPUT(bhi >> (32 - 24));
+
+	// Second output byte
+	DECODE(c);
+	blo = (bhi << 24) | (mw_uint32_t)c << 25;
+	DECODE(c);
+	blo |= (mw_uint32_t)c << 20;
+	OUTPUT(blo >> 24);
+
+	// Third output byte
+	DECODE(c);
+	blo |= (mw_uint32_t)c << 15;
+	OUTPUT(blo >> 16);
+
+	// Fourth output byte
+	DECODE(c);
+	blo |= (mw_uint32_t)c << 10;
+	DECODE(c);
+	blo |= (mw_uint32_t)c << 5;
+	OUTPUT(blo >> 8);
+
+	// Fifth output byte
+	DECODE(c);
+	blo |= (mw_uint32_t)c << 0;
+	OUTPUT(blo >> 0);
+    }
+
+    // Encountered terminator or illegal character.
+    // Return actual amount of input string and buffer space consumed.
+    *out_size = b - (mw_uint8_t*)out_buf;
+    return s - str;
 }
diff --git a/lib/base32.h b/lib/base32.h
index 729d39d..7feecbe 100644
--- a/lib/base32.h
+++ b/lib/base32.h
@@ -17,12 +17,18 @@
 
 #include "milkwayint.h"
 
+size_t
+mw_base32_encode_length(size_t len);
+
+size_t
+mw_base32_decode_length(size_t len);
+
 int
-mw_base32_encode(void *in, size_t inlen,
-		 void *out, size_t *outlen);
+mw_base32_encode(const void *in, size_t inlen,
+		 char *out, size_t outlen);
 
 int
-mw_base32_decode(void *in, size_t inlen,
-		 void *out, size_t outlen);
+mw_base32_decode(const char *in, size_t inlen,
+		 void *out, size_t *outlen);
 
 #endif