字符编码（Character Encoding）

Algorithm

December 20, 2022

1st revision at 2025-01-01

序言

每次谈到技术标准的问题，就一定要探究一下相关历史，这样才能搞清楚一堆相关概念到底是什么意思，才能理解这个标准的意义到底在哪儿。

通常这个历史发展有三个阶段：

蛮荒时期，各参与实体相对独立开发，各有各的标准；
过渡时期，为适应相关领域的发展，开始有一个统一的标准，但各实体的标准还继续起作用；
大一统时期，统一的标准已经统一了应用，蛮荒时期的标准被废弃，只存在于个别非常旧的应用里

对于字符编码这一领域，形成的统一标准是 Unicode¹ ，它

首先是一个抽象字符的码点（code point）方案，就是对每个字符编一个对应的数字编号；
其次还提供了如何把字符编号转换成二进制的字节数据的官方编码方案 (Unicode Transformation Format)： UTF-8，UTF-16

Unicode 里的字符指得是“同义“而不是“同象“，“象”问题交给排版渲染系统，不过也存在为了兼容做出的特例，比如 CJK（中日韩）字符集里的宽字符标点符号等等，也就是仍然重复编码了一些抽象上同语义的字符。

Unicode 码点方案

码点空间

码点编号的空间是 $[0, \text{0x10FFFF}]$ ，也就是 $0-\text{0x10}$ 共 $17$ 个 $0-\text{0xFFFF}$ ，也就是 $17 * 2^{16}$ 。

码点平面（plane）

每个 $2^{16}$ 代表一个平面，这样编号了 $17$ 个平面，其中标号 $0$ 的平面用于基本字符的分配，这个平面也被叫做基本平面（BMP，Basic Multilingual Plane），而其他的平面叫做补充平面（Supplementary Planes）。

码点块（Block）

每个平面又可以划分成块儿并唯一命名，每个块大小不一，但都是 $16$ 的倍数，也就是起始点都是十六进制的 $0$，也就是 $\text{0xXXX0}$ 。

UTF-8 编码²

以单字节为单位的变长编码

Bytes Number	Patten	Code Point
one byte	$\text{0xxxxxxx}$	$[0, \text{0x80})$
two bytes	$\text{110xxxxx 10xxxxxx}$	$[\text{0x80}, \text{0x800})$
three bytes	$\text{1110xxxx 10xxxxxx 10xxxxxx}$	$[\text{0x800}, \text{0x1_0000})$
four bytes	$\text{11110xxx 10xxxxxx 10xxxxxx 10xxxxxx}$	$[\text{0x01_0000}, \text{0x10_0000})$

实现范例

use UTF8DecodeError::*;
use UTF8EncodeError::*;

////////////////////////////////////////////////////////////////////////////////
//// Macros

macro_rules! parse_array {
    ($bytes:expr, $n:expr) => { {
        let cached_value = &$bytes;
        let n = $n;

        if cached_value.len() >= n {
            Ok(cached_value[..n].try_into().unwrap())
        } else {
            Err(UnfinishedByteSeq {
                expect: n,
                found: cached_value.len(),
            })
        }
    } };
}

macro_rules! check_continuation_byte {
    ($b:expr, expect=$expect:literal, found=$found:literal) => {
        {
            let b = $b;

            if b >= 0x80 && b < 0xC0 {
                Ok(())
            }
            else {
                Err(UnfinishedByteSeq {
                    expect: $expect,
                    found: $found,
                })
            }
        }
    };
}

////////////////////////////////////////////////////////////////////////////////
//// Structures

#[derive(Debug)]
pub enum UTF8DecodeError {
    InvalidStartByte(u8),
    UnfinishedByteSeq { expect: usize, found: usize },
}

#[derive(Debug)]
pub enum UTF8EncodeError {
    Overflow(u32),
}

////////////////////////////////////////////////////////////////////////////////
//// Functions

pub fn encode_utf8(
    chars: impl Iterator<Item = char>,
) -> Result<Vec<u8>, UTF8EncodeError> {
    let mut bytes = vec![];

    for ch in chars {
        encode_utf8_cp(&mut bytes, ch as _)?;
    }

    Ok(bytes)
}

pub fn encode_utf8_cp(
    bytes: &mut Vec<u8>,
    ch: u32,
) -> Result<(), UTF8EncodeError> {
    // for U+uvwxyz
    Ok(match ch {
        ..0x0080 => bytes.push(ch as _),
        0x0080..0x0800 => {
            // 110xxxyy 10yyzzzz
            // 5 + 6 bit

            let b2 = 0x80 | (ch & 0x3F) as u8;
            let b1 = 0xC0 | ((ch >> 6) & 0x1F) as u8;

            bytes.extend_from_slice(&[b1, b2]);
        }
        0x00_0800..0x01_0000 => {
            // 1110wwww 10xxxxyy 10yyzzzz
            // 4 + 6 * 2 = 16

            let b3 = 0x80 | (ch & 0x3F) as u8;
            let b2 = 0x80 | ((ch >> 6) & 0x3F) as u8;
            let b1 = 0xE0 | ((ch >> 12) & 0x0F) as u8;

            bytes.extend_from_slice(&[b1, b2, b3]);
        }
        0x01_0000..0x10_0000 => {
            // 11110uvv 10vvwwww 10xxxxyy 10yyzzzz
            // 3 + 6 * 3 = 21

            let b4 = 0x80 | (ch & 0x3F) as u8;
            let b3 = 0x80 | ((ch >> 6) & 0x3F) as u8;
            let b2 = 0x80 | ((ch >> 12) & 0x3F) as u8;
            let b1 = 0xF0 | ((ch >> 18) & 0x07) as u8;

            bytes.extend_from_slice(&[b1, b2, b3, b4]);
        }
        0x10_0000.. => Err(Overflow(ch))?,
    })
}

pub fn decode_utf8(bytes: &[u8]) -> Result<String, UTF8DecodeError> {
    let mut s = String::new();

    let mut ptr = bytes;

    while !ptr.is_empty() {
        let (ch, nbytes) = decode_utf8_cp(ptr)?;

        s.push(ch);
        ptr = &ptr[nbytes..];
    }

    Ok(s)
}

pub fn decode_utf8_cp(bytes: &[u8]) -> Result<(char, usize), UTF8DecodeError> {
    let [b1] = parse_array!(bytes, 1)?;

    Ok(match b1 {
        // 0yyyzzzz
        ..0x80 => (b1 as _, 1),
        0x80..0xC0 => Err(InvalidStartByte(b1))?,
        // 110xxxyy 10yyzzzz
        0xC0..0xE0 => {
            let [b2] = parse_array!(bytes[1..], 1)?;

            check_continuation_byte!(b2, expect=2, found=1)?;

            let ch = ((b1 as u32 & 0x1F) << 6) | (b2 as u32 & 0x3F);

            (ch.try_into().unwrap(), 2)
        }
        // 1110wwww 10xxxxyy 10yyzzzz
        0xE0..0xF0 => {
            let [b2, b3] = parse_array!(bytes[1..], 2)?;

            check_continuation_byte!(b2, expect=3, found=1)?;
            check_continuation_byte!(b3, expect=3, found=2)?;

            let ch = (b1 as u32 & 0x0F) << 12
                | (b2 as u32 & 0x3F) << 6
                | b3 as u32 & 0x3F;

            (ch.try_into().unwrap(), 3)
        }
        // 11110uvv 10vvwwww 10xxxxyy 10yyzzzz
        0xF0..0xF8 => {
            let [b2, b3, b4] = parse_array!(bytes[1..], 3)?;

            check_continuation_byte!(b2, expect=4, found=1)?;
            check_continuation_byte!(b3, expect=4, found=2)?;
            check_continuation_byte!(b4, expect=4, found=3)?;

            let ch = (b1 as u32 & 0x07) << 18
                | (b2 as u32 & 0x3F) << 12
                | (b3 as u32 & 0x3F) << 6
                | b4 as u32 & 0x3F;

            (ch.try_into().unwrap(), 4)
        }
        0xF8.. => Err(InvalidStartByte(b1))?,
    })
}

UTF-16

编码方案根据码点分为两类：

对于基本平面（Basic Multilingual Plane，BMP）中的码点，可以直接用对应 $4 \times 4=16$ bit 单元表示的数字代表，不过实际的表示范围要小一点，是 $\text{0000 - D7FF}$ 和 $\text{E000 - FFFF}$；
对于补充平面上的码点方法如下：

\[\begin{array}{l} \texttt{let}\ \text{codepoint U}\\ \texttt{let}\ \text{U'} \gets \text{U - 0x10000}\\ \texttt{let}\ \text{yyyyyyyyyyxxxxxxxxxx} \gets \text{U' \\\\ 10+10 bit} \\ \\ \texttt{Encode Into:} \\ \\ \text{1101\_10yy yyyyyyyy} \\ \text{1101\_11xx xxxxxxxx} \end{array}\]

共 $10+10=20$ 位，覆盖 $16$ 个补充平面

字节序

一般地讲字节序（大端/小端），指的是实现内部“字”（word）的字节顺序，和某个标准的设计是无关的。

比如前面 UTF-8 的编码方案直接使用字节（Byte）为单位，就不涉及字节序的问题；

反过来这里的 UTF-16 的编码方案因为使用了 u16 为单位，那么这个 u16 内部的字节排列就涉及了字节序的问题。

实现范例

pub const BOM_U16_LE: u16 = 0xFFFE;
pub const BOM_U16_BE: u16 = 0xFEFF;

use UTF16Char::*;
use UTF16EncodeError::*;
use UTF16DecodeError::*;

////////////////////////////////////////////////////////////////////////////////
//// Macros

macro_rules! split_u16 {
    ($expr:expr) => { {
        let cached_value = $expr as u16;
        &[
            (cached_value & 0xFF) as u8,
            ((cached_value & 0xFF00) >> 8) as u8,
        ]
    } };
}

macro_rules! parse_2_array {
    ($bytes:expr) => { {
        let cached_value = &$bytes;

        if cached_value.len() >= 2 {
            Ok(cached_value[..2].try_into().unwrap())
        } else {
            Err(MalformedLength(cached_value.len()))
        }
    } };
}

////////////////////////////////////////////////////////////////////////////////
//// Structures

#[derive(Debug)]
pub enum UTF16EncodeError {
    Surrogate(u16),
    /// code point > 0x10_FF_FF
    Overflow(u32),
}

#[derive(Debug)]
pub enum UTF16DecodeError {
    UnpairedSurrogate(u16),
    MalformedLength(usize),
}

#[derive(Debug)]
pub enum UTF16Char {
    /// Basic Multilingual Plane
    BMP(u16),

    /// Supplementary Multilingual Plane
    ///
    /// High surrogates, Low surrogates
    SMP(u16, u16),
}

////////////////////////////////////////////////////////////////////////////////
//// Functions

pub fn encode_utf16_le(
    chars: impl Iterator<Item = char>,
) -> Result<Vec<u8>, UTF16EncodeError> {
    let mut bytes = vec![];

    for ch in chars {
        encode_utf16_cp_le(&mut bytes, ch as _)?;
    }

    Ok(bytes)
}

pub fn encode_utf16_be(
    chars: impl Iterator<Item = char>,
) -> Result<Vec<u8>, UTF16EncodeError> {
    let mut bytes = vec![];

    for ch in chars {
        encode_utf16_cp_be(&mut bytes, ch as _)?;
    }

    Ok(bytes)
}

pub fn encode_utf16_cp_le(
    bytes: &mut Vec<u8>,
    ch: u32,
) -> Result<(), UTF16EncodeError> {
    match encode_utf16_cp_(ch)? {
        BMP(w) => bytes.extend_from_slice(split_u16!(w)),
        SMP(w1, w2) => {
            let &[b0, b1] = split_u16!(w1);
            let &[b2, b3] = split_u16!(w2);

            bytes.extend_from_slice(&[b0, b1, b2, b3]);
        }
    }

    Ok(())
}

pub fn encode_utf16_cp_be(
    bytes: &mut Vec<u8>,
    ch: u32,
) -> Result<(), UTF16EncodeError> {
    match encode_utf16_cp_(ch)? {
        BMP(w) => {
            let &[b0, b1] = split_u16!(w);
            bytes.extend_from_slice(&[b1, b0]);
        }
        SMP(w1, w2) => {
            let &[b0, b1] = split_u16!(w1);
            let &[b2, b3] = split_u16!(w2);

            bytes.extend_from_slice(&[b1, b0, b3, b2]);
        }
    }

    Ok(())
}

fn encode_utf16_cp_(ch: u32) -> Result<UTF16Char, UTF16EncodeError> {
    match ch {
        ..0xD800 | 0xE000..0x01_0000 => Ok(BMP(ch as _)),
        0xD800..0xE000 => Err(Surrogate(ch as _)),
        0x01_00_00..0x11_00_00 => {
            // U' = yyyyyyyyyyxxxxxxxxxx  // U - 0x10000
            // W1 = 110110yyyyyyyyyy      // 0xD800 + yyyyyyyyyy high surrogate
            // W2 = 110111xxxxxxxxxx      // 0xDC00 + xxxxxxxxxx low surrogate

            // 0x00_00_00 - 0x0F_FF_FF
            let ch = ch - 0x01_00_00;

            // high unit 0b_1101_11_00_0000_0000, 0xDC00
            let unit_hi: u16 = 0xD800 | ((ch >> 10) & 0x3FF) as u16;

            // low unit
            // 0b_1101_10_00_0000_0000 (10 bit) ..., 0xD800
            let unit_lo: u16 = 0xDC00 | (ch & 0x3FF) as u16;

            Ok(SMP(unit_hi, unit_lo))
        }
        0x11_00_00.. => Err(Overflow(ch)),
    }
}

pub fn decode_utf16_le(bytes: &[u8]) -> Result<String, UTF16DecodeError> {
    let mut s = String::new();

    let mut ptr = bytes;

    while !ptr.is_empty() {
        let (ch, nbytes) = decode_utf16_cp_le(ptr)?;

        s.push(ch);
        ptr = &ptr[nbytes..];
    }

    Ok(s)
}

pub fn decode_utf16_be(bytes: &[u8]) -> Result<String, UTF16DecodeError> {
    let mut s = String::new();

    let mut ptr = bytes;

    while !ptr.is_empty() {
        let (ch, nbytes) = decode_utf16_cp_be(ptr)?;

        s.push(ch);
        ptr = &ptr[nbytes..];
    }

    Ok(s)
}

pub fn decode_utf16_cp_le(
    bytes: &[u8],
) -> Result<(char, usize), UTF16DecodeError> {
    let w = u16::from_le_bytes(
        parse_2_array!(bytes)?,
    );

    Ok(match w {
        ..0xD800 | 0xE000.. => (decode_utf16_cp_(BMP(w)), 2),
        // high surrogate
        0xD800..0xDC00 => {
            let w2 =
                u16::from_le_bytes(parse_2_array!(bytes[2..])?);

            (decode_utf16_cp_(SMP(w, w2)), 4)
        }
        // low surrogate
        0xDC00..0xE000 => Err(UnpairedSurrogate(w))?,
    })
}

pub fn decode_utf16_cp_be(
    bytes: &[u8],
) -> Result<(char, usize), UTF16DecodeError> {
    let w = u16::from_be_bytes(
        parse_2_array!(bytes)?,
    );

    Ok(match w {
        ..0xD800 | 0xE000.. => (decode_utf16_cp_(BMP(w)), 2),
        // high surrogate
        0xD800..0xDC00 => {
            let w2 =
                u16::from_be_bytes(parse_2_array!(bytes[2..])?);

            (decode_utf16_cp_(SMP(w, w2)), 4)
        }
        // low surrogate
        0xDC00..0xE000 => Err(UnpairedSurrogate(w))?,
    })
}

fn decode_utf16_cp_(utf16char: UTF16Char) -> char {
    match utf16char {
        BMP(w) => w as u32,
        SMP(w1, w2) => {
            (((w1 & 0x3FF) << 10) | (w2 & 0x3FF)) as u32 + 0x01_00_00
        }
    }
    .try_into()
    .unwrap()
}

这个实现是考虑已知字节序是小段序的情况，关于 Unicode 有一个 BOM的概念，用来暗示字节序，如下面介绍。

BOM（Byte order mark）

BOM 是放在文本流的开头，有特殊用途特别的 Unicode 字符：

声明字节序
表明文本具有很高置信水平地采用了 Unicode 编码
声明具体的 Unicode 编码方案

UTF-16 ：UTF-16 小端序 FF FE ，UTF-16 大端序 FE FF

UTF-8：EF BB BF

GB18030：84 31 95 33

主要有用的是 UTF-16，因为对基本平面上的码点使用了双字节的数字表示，需要明确字节序才能正确编码，而诸如 UTF-8 通常就不加 BOM ，因为显然字节序可以很容易地探测出来。

GB18030

具体标准可在国家标准网站查询

最早的码点并编码方案是1980年的 GB2312，双字节，构成，主要是简体和部分繁体以及其他国语言³；
在1984年，台湾地区的五家厂商退出了繁体字编码的 Big5 ，这两个编码的转换问题是早期繁体中文游戏经常面临的问题；
在1993年，随着 Unicode 1.1 的出现，国标推出了对应的 GB13000.1-93 ， GBK 就是一个利用 GB2312 未使用码点装载 GB13000.1-93 中字符的 GB2312 拓展；
在2000年，GB18030 第一版发布，到最新版，已经实现了 Unicode 所有码点：单字节用于英欧字符，双字节用于兼容 GBK ，四字节用于编码其他 Unicode ；
也许等到这个标准进一步成熟和普及的时候可以深入地看下实现细节

比较

首先虽然具体码点不一样，但 GB18030 毕竟编码了 Unicode 标准下的所有字符，也可以算某种非官方的 UTF 实现。

比较 UTF-8，UTF-16 和 GB18030：

UTF-16首先出局，它在任何情况下的空间性能都差于 GB18030；
对于东亚字符 GB18030 显然是最好的选择；
其他，视情况而定，如果字符在拓展 GBK 中，那么 GB18030 仍然是最好的，否则如果在 UTF-8 下能用三字节表示，那就是 UTF-8 更优，如果 UTF-8 也是四字节表示，那就相当。

引用

https://en.wikipedia.org/wiki/Unicode ↩
https://en.wikipedia.org/wiki/UTF-8 ↩
https://en.wikipedia.org/wiki/GB_2312 ↩

字符编码（Character Encoding）

序言

Unicode 码点方案

码点空间

码点平面（plane）

码点块（Block）

UTF-8 编码2

实现范例

UTF-16

字节序

实现范例

BOM（Byte order mark）

GB18030

比较

引用

UTF-8 编码²