buffer: optimize decoding wrapped base64 data

The fast base64 decoder used to switch to the slow one permanently when it saw a whitespace or other garbage character. Since the most common situation such characters may be encountered in is line-wrapped base64 data, a more profitable strategy is to decode a single 24-bit group with the slow decoder and then continue running the fast algorithm. PR-URL: #12146 Ref: #12114 Reviewed-By: Anna Henningsen <anna@addaleax.net> Reviewed-By: Trevor Norris <trev.norris@gmail.com> Reviewed-By: James M Snell <jasnell@gmail.com>
nodejs · italoacasas · Apr 11, 2017 · Apr 7, 2017 · Dec 16, 2016 · Mar 27, 2017
commit 805ebef8b160b7fd3c003ba7e30aec8f92fea67f
diff --git a/benchmark/buffers/buffer-base64-decode-wrapped.js b/benchmark/buffers/buffer-base64-decode-wrapped.js
@@ -0,0 +1,26 @@
+'use strict';
+
+const common = require('../common.js');
+
+const bench = common.createBenchmark(main, {
+  n: [32],
+});
+
+function main(conf) {
+  const n = +conf.n;
+  const charsPerLine = 76;
+  const linesCount = 8 << 16;
+  const bytesCount = charsPerLine * linesCount / 4 * 3;
+
+  const line = 'abcd'.repeat(charsPerLine / 4) + '\n';
+  const data = line.repeat(linesCount);
+  // eslint-disable-next-line no-unescaped-regexp-dot
+  data.match(/./);  // Flatten the string
+  const buffer = Buffer.alloc(bytesCount, line, 'base64');
+
+  bench.start();
+  for (var i = 0; i < n; i++) {
+    buffer.base64Write(data, 0, bytesCount);
+  }
+  bench.end(n);
+}
diff --git a/src/base64.h b/src/base64.h
@@ -52,36 +52,33 @@ extern const int8_t unbase64_table[256];
 
 
 template <typename TypeName>
-size_t base64_decode_slow(char* dst, size_t dstlen,
-                          const TypeName* src, size_t srclen) {
+bool base64_decode_group_slow(char* const dst, const size_t dstlen,
+                              const TypeName* const src, const size_t srclen,
+                              size_t* const i, size_t* const k) {
   uint8_t hi;
   uint8_t lo;
-  size_t i = 0;
-  size_t k = 0;
-  for (;;) {
 #define V(expr)                                                               \
-    for (;;) {                                                                \
-      const uint8_t c = src[i];                                               \
-      lo = unbase64(c);                                                       \
-      i += 1;                                                                 \
-      if (lo < 64)                                                            \
-        break;  /* Legal character. */                                        \
-      if (c == '=' || i >= srclen)                                            \
-        return k;                                                             \
-    }                                                                         \
-    expr;                                                                     \
-    if (i >= srclen)                                                          \
-      return k;                                                               \
-    if (k >= dstlen)                                                          \
-      return k;                                                               \
-    hi = lo;
-    V(/* Nothing. */);
-    V(dst[k++] = ((hi & 0x3F) << 2) | ((lo & 0x30) >> 4));
-    V(dst[k++] = ((hi & 0x0F) << 4) | ((lo & 0x3C) >> 2));
-    V(dst[k++] = ((hi & 0x03) << 6) | ((lo & 0x3F) >> 0));
+  for (;;) {                                                                  \
+    const uint8_t c = src[*i];                                                \
+    lo = unbase64(c);                                                         \
+    *i += 1;                                                                  \
+    if (lo < 64)                                                              \
+      break;  /* Legal character. */                                          \
+    if (c == '=' || *i >= srclen)                                             \
+      return false;  /* Stop decoding. */                                     \
+  }                                                                           \
+  expr;                                                                       \
+  if (*i >= srclen)                                                           \
+    return false;                                                             \
+  if (*k >= dstlen)                                                           \
+    return false;                                                             \
+  hi = lo;
+  V(/* Nothing. */);
+  V(dst[(*k)++] = ((hi & 0x3F) << 2) | ((lo & 0x30) >> 4));
+  V(dst[(*k)++] = ((hi & 0x0F) << 4) | ((lo & 0x3C) >> 2));
+  V(dst[(*k)++] = ((hi & 0x03) << 6) | ((lo & 0x3F) >> 0));
 #undef V
-  }
-  UNREACHABLE();
+  return true;  // Continue decoding.
 }
 
 
@@ -90,8 +87,8 @@ size_t base64_decode_fast(char* const dst, const size_t dstlen,
                           const TypeName* const src, const size_t srclen,
                           const size_t decoded_size) {
   const size_t available = dstlen < decoded_size ? dstlen : decoded_size;
-  const size_t max_i = srclen / 4 * 4;
   const size_t max_k = available / 3 * 3;
+  size_t max_i = srclen / 4 * 4;
   size_t i = 0;
   size_t k = 0;
   while (i < max_i && k < max_k) {
@@ -102,16 +99,20 @@ size_t base64_decode_fast(char* const dst, const size_t dstlen,
         unbase64(src[i + 3]);
     // If MSB is set, input contains whitespace or is not valid base64.
     if (v & 0x80808080) {
-      break;
+      const size_t old_i = i;
+      if (!base64_decode_group_slow(dst, dstlen, src, srclen, &i, &k))
+        return k;
+      max_i = old_i + (srclen - i) / 4 * 4;  // Align max_i again.
+    } else {
+      dst[k + 0] = ((v >> 22) & 0xFC) | ((v >> 20) & 0x03);
+      dst[k + 1] = ((v >> 12) & 0xF0) | ((v >> 10) & 0x0F);
+      dst[k + 2] = ((v >>  2) & 0xC0) | ((v >>  0) & 0x3F);
+      i += 4;
+      k += 3;
     }
-    dst[k + 0] = ((v >> 22) & 0xFC) | ((v >> 20) & 0x03);
-    dst[k + 1] = ((v >> 12) & 0xF0) | ((v >> 10) & 0x0F);
-    dst[k + 2] = ((v >>  2) & 0xC0) | ((v >>  0) & 0x3F);
-    i += 4;
-    k += 3;
   }
   if (i < srclen && k < dstlen) {
-    return k + base64_decode_slow(dst + k, dstlen - k, src + i, srclen - i);
+    base64_decode_group_slow(dst, dstlen, src, srclen, &i, &k);
   }
   return k;
 }