LOGI

Common Encoding Implementation

本文将介绍几种常见信息编码标准,并用 JavaScript 对其实现,包括 UTF-8,Base58, Base64, URL Encode。

UTF-8

在 Unicode(统一码)系统中,每个字符对应一个码点(一个无符号整数)。一段文本中所有字符对应一段码点序列,通过某种转换,可将序列映射为若干字节,以便进行存储和网络间传输。UTF(the Unicode Transformation Format)统一码转换格式,即是一类映射方法,包括 UTF-8,UTF-16, UTF-32, UTF-EBCDIC。其中的 UTF-8 是一种变长 Unicode 编码方法,其将不同 Unicode 码点存储为 1 到 4 字节不等的单元,对于 ASCII 码点范围,使用 1 字节编码,以兼容 ASCII,变长有利于节省空间。下表给出了从 Unicode 码点到 UTF-8 编码的转换规则。

First code pointLast code pointByte 1Byte 2Byte 3Byte 4
U+0000U+007F0xxxxxxx
U+0080U+07FF110xxxxx10xxxxxx
U+0800U+FFFF1110xxxx10xxxxxx10xxxxxx
U+10000U+10FFFF11110xxx10xxxxxx10xxxxxx10xxxxxx

例如,汉字 “中” 的 Unicode 码点为 \u4e2d,位于上表第三行范围,因此需要 3 字节存储,将其二进制 0100 1110 0010 1101 各位从高到低依次取出,置于上表第三行的 xxxx 处,即完成编码。编码后的二进制为 1110 0100 1011 1000 1010 1101,十六进制为 \xe4\xb8\xad

用代码实现也比较简单,翻译上表即可。

function unicodeArrToUtf8Arr(unicodeArr) {
  const buf = [];
  for (const code of unicodeArr) {
    let rest = 0;

    // encode the first byte
    if (code < 0x80) {
      // 0xxxxxxx
      buf.push(code);
    } else if (code < 0x800) {
      // 110xxxxx 10xxxxxx
      buf.push((0b110 << 5) | (code >> 6));
      rest = 1;
    } else if (code < 0x10000) {
      // 1110xxxx 10xxxxxx 10xxxxxx
      buf.push((0b1110 << 4) | (code >> 12));
      rest = 2;
    } else {
      // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
      buf.push((0b11110 << 3) | (code >> 18));
      rest = 3;
    }

    // encode the rest bytes
    while (rest-- > 0) {
      buf.push((0b10 << 6) | ((code >> (rest * 6)) & 0x3f));
    }
  }
  return buf;
}

以下是解码规则,是编码的逆操作。

function utf8ArrToUnicodeArr(utf8Arr) {
  const buf = [];
  for (let i = 0; i < utf8Arr.length;) {
    let _1 = utf8Arr[i++];
    let rest = 0;

    // decode the first byte
    if (_1 >> 7 === 0) {
      // 0xxxxxxx
      _1 &= 0b01111111;
    } else if (_1 >> 5 === 0b110) {
      // 110xxxxx 10xxxxxx
      rest = 1;
      _1 &= 0b00011111;
    } else if (_1 >> 4 === 0b1110) {
      // 1110xxxx 10xxxxxx 10xxxxxx
      rest = 2;
      _1 &= 0b00001111;
    } else {
      // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
      rest = 3;
      _1 &= 0b00000111;
    }

    // combine the rest bytes
    _1 <<= rest * 6;
    while (rest-- > 0) {
      _1 |= (utf8Arr[i++] & 0x3f) << (rest * 6);
    }
    buf.push(_1);
  }
  return buf;
}

BaseN

BaseN 是一类 binary-to-text(二进制转文本)编码方法,其用 N 种字符表示二进制数据,包括 Base64, Base58 等。其实质是将编码后的字符串看成一个 N 进制整数,每个字符对应整数的一位。例如,十进制数 255 是 Base10 编码,其 Base2 编码即为其二进制 1111 1111,Base8 编码即为其八进制 377,Base16 编码即为其十六进制 FF,以此类推。

Base58

顾名思义,Base58 使用 58 种字符编码数据,其知名用途是比特币的钱包地址编码,中本聪在代码注释中给出了他的使用意图。

  1. 避免混淆。在某些字体下,数字 0 和字母大写 O,以及字母大写 I 和字母小写 l 会非常相似。
  2. 不使用 "+" 和 "/" 的原因是非字母或数字的字符串作为帐号较难被接受。
  3. 没有标点符号,通常不会被从中间分行。
  4. 大部分的软件支持双击选择整个字符串。

以下是 Base58 码表。

ValueCharacterValueCharacterValueCharacterValueCharacter
01122334
45566778
899A10B11C
12D13E14F15G
16H17J18K19L
20M21N22P23Q
24R25S26T27U
28V29W30X31Y
32Z33a34b35c
36d37e38f39g
40h41i42j43k
44m45n46o47p
48q49r50s51t
52u53v54w55x
56y57z

上文提到 BaseN 编码的实质是将数据当成一个整数后转为 N 进制形式。扩展 ASCII 字符共 256 个,因此使用 ASCII 编码的字符串可看成一个 256 进制整数。例如,字符串 js 可当成一个 256 进制整数,其大小为 ascii(j) * 256 + ascii(s) = 106 * 256 + 115 = 27251 = 8 * 58^2 + 5 * 58^1 + 49,因此其 58 进制有 3 位,位值分别为 8,5,49,通过查 Base58 表,编码后的字符串为 96r 表示。

以上做法存在一个问题,如果 ASCII 编码字符串有若干 \0 前缀,由于 ascii(\0) = 0,如果把该字符串看成 256 进制整数,这些 \0 并不影响数值大小,例如,十进制 00012345 = 12345。即若完全按照进制转换方法编码,前导零值将丢失,虽然前导零不影响整数大小,但在原始二进制数据中一定有其存在意义,丢失是我们不愿看到的。为此,可在转换前数出前导零值个数,转换后补上相同个数的前导零值,这样就能将信息无损编码。

理解以上过程即可编写 Base58 编解码类。

class BxxConverter {
  static countLeadingElem(iter, obj) {
    let i = 0;
    for (; i < iter.length && iter[i] === obj; i++);
    return i;
  }

  static convert(fromBuf, fromBase, toBase) {
    const zeros = BxxConverter.countLeadingElem(fromBuf, 0);

    // convert a base xx buf to a base 10 big integer x
    let x = BigInt.fromBxxBuf(fromBuf.slice(zeros), fromBase);
    let r = 0;

    let buf = [];
    // calculate every position of x when converted to the object base number
    while (!x.isZero()) {
      // r = x % toBase, that's the current position
      [x, r] = x.div(toBase);
      buf.push(r);
    }

    if (zeros > 0) buf = buf.concat(new Array(zeros).fill(0));

    return buf.reverse();
  }
}

上述代码使用了大数类将原始数据转为十进制,再通过反复除 toBase 取余获得目标进制的每一位。实际上可以省去转十进制过程,直接做 fromBase 进制除法,相当于模拟高精度计算时的压位操作,读者可自行搜索。

Base64

理论上 Base64 也可使用以上通用方法转换,但对于以 2 的 n 次幂为基底的编码互转,有更简便的方法,可避免 BigInt 类的使用。这得益于以下观察:

二进制转八进制,只需将每 3 位看成一组,其十进制值即为一个八进制位。二进制转十六进制,只需将每 4 位看成一组,其十进制值即为一个十六进制位。依此类推,二进制转 64 进制,只需将每 6 位看成一组,其十进制值即为一个 64 进制位。

因此,要将任意二进制数据(以字节数组形式表示)转为 Base64,只需以每 6 位为一组,得到 64 进制下的码点,通过查表得到相应字符。反过来,要解码 Base64 字符串为二进制数据,只需将每个码点依次扩展为 6 位二进制,再以 8 位分组,得到相应字节。

需要注意的是,n 字节二进制数据共 8n 位,如果不能被 6 整除,以 6 位为一组,最后一组需要补充 6 - 8n % 6 位个 0。但在 Base64 标准中,为了填充的是整数字节(八位),且为了能在编码中直接看出填充的字节数,规定最后完全由填充形成的若干全零 6 位组,编码为 =,其个数等于填充的字节数。

r = 8n % 6,当其为 0 时无需填充,否则设需要填充 k 字节,则剩余的位数加上填充的位数等于 r + 8k = 6 + 6k,解得 k = 3 - r/2。由于 0 < r < 6,因此 0 < r / 2 < 3,只能取 1, 2。当 r/2 = 1 时,需要填充 2 字节,完全由填充形成的 6 位组也等于 2。当 r/2 = 2 时,需要填充 1 字节,完全由填充形成的 6 位组也等于 1。由于 8 和 6 的最小公倍数是 24,因此,可以把每 3 = 24 / 8 个字节当成一个最小批处理单元,编码为 4 = 24 / 6 个 Base64 码点。

举个例子,文本 A 的 ASCII 码为 65,二进制 0100 0001,占 1 字节。编码为 Base64 时,要填充 3 - 4 % 3 = 2 个全零字节,变为 0100 0001 0000 0000 0000 0000。以 6 位为一组编码为 Base64 刚好 4 个码点,分别是

通过查表,16 对应 Q,而最后两组完全是由填充形成的,因此最终编码为 QQ==。以下是 Base64 码表

                      Table 1: The Base 64 Alphabet

     Value Encoding  Value Encoding  Value Encoding  Value Encoding
         0 A            17 R            34 i            51 z
         1 B            18 S            35 j            52 0
         2 C            19 T            36 k            53 1
         3 D            20 U            37 l            54 2
         4 E            21 V            38 m            55 3
         5 F            22 W            39 n            56 4
         6 G            23 X            40 o            57 5
         7 H            24 Y            41 p            58 6
         8 I            25 Z            42 q            59 7
         9 J            26 a            43 r            60 8
        10 K            27 b            44 s            61 9
        11 L            28 c            45 t            62 +
        12 M            29 d            46 u            63 /
        13 N            30 e            47 v
        14 O            31 f            48 w         (pad) =
        15 P            32 g            49 x
        16 Q            33 h            50 y

以下是编解码实现。解码时,首先把后缀的若干 = 号去掉,因为它们完全是填充形成的,肯定不属于原始数据。此时 Base64 字符串最多只包含不足一字节的填充位,由于原始数据的字节数是整数,因此一定有 rawLen = floor(len(b64Str) * 6 / 8),只要不断取 8 位单元,取完 rawLen 个字节即完成解码。

class Base64 {
  static b64CodeToAsciiCode(u6) {
    if (u6 < 26) {
      return u6 + 'A'.codePointAt(0);
    } else if (u6 < 52) {
      return u6 - 26 + 'a'.codePointAt(0);
    } else if (u6 < 62) {
      return u6 - 52 + '0'.codePointAt(0);
    } else if (u6 < 64) {
      return '+/'.codePointAt(u6 - 62);
    } else {
      throw new Error(`Invalid base64 code point: ${u6}.`);
    }
  }

  static asciiCharToB64Code(chr) {
    const diff = (c) => chr.codePointAt(0) - c.codePointAt(0);

    if (chr >= 'A' && chr <= 'Z') {
      return diff('A');
    } else if (chr >= 'a' && chr <= 'z') {
      return diff('a') + 26;
    } else if (chr >= '0' && chr <= '9') {
      return diff('0') + 52;
    } else if (chr === '+') {
      return 62;
    } else if (chr === '/') {
      return 63;
    } else {
      throw new Error(`Can't convert to base64 code from ASCII char: ${chr}.`);
    }
  }

  static encode(u8Arr) {
    let out = '';

    let mod = 2;
    for (let i = 0, u24 = 0; i < u8Arr.length; i++) {
      mod = i % 3;
      u24 |= u8Arr[i] << ((16 >> mod) & 24) /* 8 * (2 - mod) */ ;
      if (mod === 2 || i === u8Arr.length - 1) {
        out += String.fromCodePoint(
          Base64.b64CodeToAsciiCode((u24 >> 18) & 0x3f),
          Base64.b64CodeToAsciiCode((u24 >> 12) & 0x3f),
          Base64.b64CodeToAsciiCode((u24 >> 6) & 0x3f),
          Base64.b64CodeToAsciiCode(u24 & 0x3f)
        );
        u24 = 0;
      }
    }
    return out.substring(0, out.length - 2 + mod) + '='.repeat(2 - mod);
  }

  static decode(b64Str) {
    let pad = 0;
    for (let i = b64Str.length - 1; i > 0; i--) {
      if (b64Str[i] !== '=') break;
      pad++;
    }
    b64Str = b64Str.slice(0, b64Str.length - pad);

    const bLen = (b64Str.length * 3) >> 2; // Math.floor(len * 6 / 8)
    const buf = new Array(bLen);
    for (let i = 0, u24 = 0, bIdx = 0; i < b64Str.length; i++) {
      const mod = i & 3; // i % 4
      u24 |= Base64.asciiCharToB64Code(b64Str[i]) << (6 * (3 - mod));
      if ((mod === 3) | (i === b64Str.length - 1)) {
        for (let j = 0; j < 3 && bIdx < bLen; j++) {
          buf[bIdx++] = (u24 >> ((16 >> j) & 24)) & 0xff;
        }
        u24 = 0;
      }
    }

    return buf;
  }
}

URL Encoding

URL 编码用于将任意数据置于 URL 中,如果不编码,这些数据将与 URL 的保留字符冲突。一个 URL 格式可表示为

URI = scheme ":" ["//" authority] path ["?" query] ["#" fragment]
authority = [userinfo "@"] host [":" port]

可见 :/?#@ 等字符具有特殊含义,编码后的数据应不包含这些字符以避免歧义。如果数据中存在这些字符,应将其转为 ASCII 码的二位十六进制形式,并在前面加上百分号。对于非 ASCII 码数据,标准建议先使用 UTF-8 对其编码。URL 编码也用于发送 application/x-www-form-urlencoded 数据。以下是相应实现

const Utf8 = require('./utf8');

module.exports = class Url {
  static specialChr = '!*();:@&=+$,/?#[]% ';
  static hex = (b) => `%${b < 16 ? '0' : ''}${b.toString(16).toUpperCase()}`;

  static encode(raw) {
    let out = '';
    for (const c of raw) {
      const p = c.codePointAt(0);

      if (p >= 0x80 || Url.specialChr.includes(c)) {
        out += Utf8.unicodeArrToUtf8Arr([p]).map(Url.hex).join('');
        continue;
      }

      out += c;
    }

    return out;
  }

  static decode(encoded) {
    let out = '';

    for (let i = 0; i < encoded.length; ) {
      if (encoded[i] === '%') {
        const utfBuf = [];
        while (i < encoded.length && encoded[i] === '%') {
          utfBuf.push(parseInt(encoded.slice(i + 1, i + 3), 16));
          i += 3;
        }
        out += Utf8.unicodeArrToJsStr(Utf8.utf8ArrToUnicodeArr(utfBuf));
        continue;
      }

      out += encoded[i++];
    }

    return out;
  }
};

Conclusion

本文简要介绍了 UTF-8,Base58, Base64, URL Encode 编码的用途,方法,和关键代码实现。具体来说,用于将 Unicode 映射为字节序列的 UTF-8 编码,使全世界大多数国家的文字能以统一方法存储到计算机。BaseN 编码用于将二进制数据编码为文本,其实质是整数间的进制转换,当 N 为 2 的幂次方时,它们之间的转换可以通过位映射完成。URL 编码用于将数据安全地编码到网址中,或通过 HTTP 传送。

本文涉及的可运行代码见 Github 仓库,文中的表述和代码可能存在错误,如有发现请在评论区留言,感谢阅读。

References

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »