[git commit] libbb/yescrypt: explain and shrink decode64_uint32()

[Denys Vlasenko]

commit: https://git.busybox.net/busybox/commit/?id=78bd8a44b75cf39ea17c8a586ba35776d835551f
branch: https://git.busybox.net/busybox/commit/?id=refs/heads/master

function                                             old     new   delta
decode64_uint32                                      177     141     -36

Signed-off-by: Denys Vlasenko <vda.linux at googlemail.com>
---
 libbb/yescrypt/alg-yescrypt-common.c | 87 +++++++++++++++++++++++++++++++-----
 libbb/yescrypt/alg-yescrypt.h        |  2 +
 2 files changed, 79 insertions(+), 10 deletions(-)

diff --git a/libbb/yescrypt/alg-yescrypt-common.c b/libbb/yescrypt/alg-yescrypt-common.c
index e5d045058..c85b2a0b9 100644
--- a/libbb/yescrypt/alg-yescrypt-common.c
+++ b/libbb/yescrypt/alg-yescrypt-common.c
@@ -27,41 +27,106 @@ static NOINLINE const uint8_t *decode64_uint32(
 		uint32_t *dst,
 		const uint8_t *src, uint32_t val)
 {
-	uint32_t start = 0, end = 47, chars = 1, bits = 0;
+	uint32_t start = 0, end = 47, bits = 0;
 	uint32_t c;
 
-	if (!src) /* prevous decode failed already? */
+	if (!src) /* previous decode failed already? */
 		goto fail;
 
 	c = a2i64(*src++);
 	if (c > 63)
 		goto fail;
 
+// The encoding of number N:
+// start = 0 end = 47
+// If N < 48, it is encoded verbatim, else
+// N -= 48
+// start = end+1 = 48
+// end += (64-end)/2 = 55
+// If N < (end+1-start)<<6 = 8<<6, it is encoded as 48+(N>>6)|low6bits (that is, 48...55|<6bit>), else
+// N -= 8<<6
+// start = end+1 = 56
+// end += (64-end)/2 = 59
+// If N < (end+1-start)<<2*6 = 4<<12, it is encoded as 56+(N>>2*6)|low12bits (that is, 56...59|<6bit>|<6bit>), else
+// ...same for 60..61|<6bit>|<6bit>|<6bit>
+// .......same for 62|<6bit>|<6bit>|<6bit>|<6bit>
+// .......same for 63|<6bit>|<6bit>|<6bit>|<6bit>|<6bit>
+	dbg_dec64("c:%d val:0x%08x", (int)c, (unsigned)val);
 	while (c > end) {
+		dbg_dec64("c:%d > end:%d", (int)c, (int)end);
 		val += (end + 1 - start) << bits;
+		dbg_dec64("val+=0x%08x", (int)((end + 1 - start) << bits));
+		dbg_dec64(" val:0x%08x", (unsigned)val);
 		start = end + 1;
-		end = start + (62 - end) / 2;
-		chars++;
+		end += (64 - end) / 2;
 		bits += 6;
+		dbg_dec64("start=%d", (int)start);
+		dbg_dec64("end=%d", (int)end);
+		dbg_dec64("bits=%d", (int)bits);
 	}
 
 	val += (c - start) << bits;
+	dbg_dec64("final val+=0x%08x", (int)((c - start) << bits));
+	dbg_dec64("       val:0x%08x", (unsigned)val);
 
-	while (--chars) {
+	while (bits != 0) {
 		c = a2i64(*src++);
 		if (c > 63)
 			goto fail;
 		bits -= 6;
 		val += c << bits;
+		dbg_dec64("low bits val+=0x%08x", (int)(c << bits));
+		dbg_dec64("          val:0x%08x", (unsigned)val);
 	}
+ ret:
 	*dst = val;
-
 	return src;
+ fail:
+	val = 0;
+	src = NULL;
+	goto ret;
+}
 
-fail:
-	*dst = 0;
-	return NULL;
+#if TEST_DECODE64
+static void test_decode64_uint32(void)
+{
+	const uint8_t *src, *end;
+	uint32_t u32;
+	int a = 48;
+	int b = 8<<6;  // 0x0200
+	int c = 4<<12; // 0x04000
+	int d = 2<<18; // 0x080000
+	int e = 1<<24; // 0x1000000
+
+	src = (void*)"wzzz";
+	end = decode64_uint32(&u32, src, 0);
+	if (u32 != 0x0003ffff+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+	if (end != src + 4) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+	src = (void*)"xzzz";
+	end = decode64_uint32(&u32, src, 0);
+	if (u32 != 0x0007ffff+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+	if (end != src + 4) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+	// Note how the last representable "x---" encoding, 0x7ffff, is exactly d-1!
+	// And if we now increment it, we get:
+	src = (void*)"y....";
+	end = decode64_uint32(&u32, src, 0);
+	if (u32 != 0x00000000+d+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+	if (end != src + 5) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+	src = (void*)"yzzzz";
+	end = decode64_uint32(&u32, src, 0);
+	if (u32 != 0x00ffffff+d+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+	if (end != src + 5) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+
+	src = (void*)"zzzzzz";
+	end = decode64_uint32(&u32, src, 0);
+	if (u32 != 0x3fffffff+e+d+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+	if (end != src + 6) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+
+	bb_error_msg("test_decode64_uint32() OK");
 }
+#else
+# define test_decode64_uint32() ((void)0)
+#endif
 
 #if 1
 static const uint8_t *decode64(
@@ -70,7 +135,7 @@ static const uint8_t *decode64(
 {
 	size_t dstpos = 0;
 
-	dbg_dec64("src:'%s' len:%d", src, (int)srclen);
+	dbg_dec64("src:'%s'", src);
 	for (;;) {
 		uint32_t c, value = 0;
 		int bits = 0;
@@ -215,6 +280,8 @@ char *yescrypt_r(
 	size_t need, prefixlen;
 	uint32_t u32;
 
+	test_decode64_uint32();
+
 	memset(yctx, 0, sizeof(yctx));
 	yctx->param.p = 1;
 
diff --git a/libbb/yescrypt/alg-yescrypt.h b/libbb/yescrypt/alg-yescrypt.h
index 4554e3de3..e558cfdc5 100644
--- a/libbb/yescrypt/alg-yescrypt.h
+++ b/libbb/yescrypt/alg-yescrypt.h
@@ -28,6 +28,7 @@
  * online backup system.
  */
 #ifdef YESCRYPT_INTERNAL
+
 # if 1
 #  define dbg(...) ((void)0)
 # else
@@ -39,6 +40,7 @@
 #  define dbg_dec64(...) bb_error_msg(__VA_ARGS__)
 # endif
 #endif
+#define TEST_DECODE64 0
 
 /**
  * Type and possible values for the flags argument of yescrypt_kdf(),