12、位操作与编码：用位运算实现Base64编码的查表优化

Base64编码，说白了就是把二进制数据转成可打印的ASCII字符。很多嵌入式通信协议里都用它，比如HTTP的Basic认证、邮件附件、甚至一些IoT设备的固件升级包。我最早接触Base64是在做一个小型网络协议栈的时候，那时候MCU的Flash和RAM都紧巴巴的，标准查表法虽然简单，但总觉得哪里可以再抠一抠性能。

今天我们就聊聊，如何用位运算来优化Base64的查表过程。这不仅仅是炫技，而是实实在在能省下几个时钟周期的事情。

Base64编码的基本原理

Base64的核心思想很简单：把3个字节（24位）拆成4组，每组6位。6位能表示0~63，正好对应64个可打印字符。标准映射表是这样的：

标准做法是：从输入流中取3个字节，用移位和掩码提取出4个6位值，然后查表得到字符。代码大概长这样：

// 标准查表法
static const char base64_table[] = 
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "abcdefghijklmnopqrstuvwxyz"
    "0123456789+/";

void base64_encode_standard(const uint8_t *input, int len, char *output) {
    int i, j;
    for (i = 0, j = 0; i < len; i += 3) {
        uint32_t triple = ((uint32_t)input[i] << 16) |
                          ((uint32_t)input[i+1] << 8) |
                          (uint32_t)input[i+2];
        output[j++] = base64_table[(triple >> 18) & 0x3F];
        output[j++] = base64_table[(triple >> 12) & 0x3F];
        output[j++] = base64_table[(triple >> 6) & 0x3F];
        output[j++] = base64_table[triple & 0x3F];
    }
}

这段代码没什么毛病，但每次查表都要访问内存。对于缓存友好的系统还好说，但在一些低端MCU上，查表可能比移位运算慢得多。我曾在Cortex-M0上测过，一次查表大约要3~4个时钟周期，而位运算只需要1个周期。

位运算优化的思路

优化的核心思路是：能不能不用查表，直接用位运算把6位值映射成字符？

你想想看，Base64的字符集其实是有规律的：

• 0~25：对应 'A'~'Z'，即 ch = idx + 'A'
• 26~51：对应 'a'~'z'，即 ch = idx - 26 + 'a'
• 52~61：对应 '0'~'9'，即 ch = idx - 52 + '0'
• 62：对应 '+'
• 63：对应 '/'

嗯，这里要注意：前三个区间是连续的，但62和63是特例。所以我们可以用条件判断来区分，但条件分支在流水线上可能会造成惩罚。更好的办法是用位运算构造一个映射函数。

我个人习惯的做法是：先计算一个偏移量，然后用加法得到字符。具体来说：

// 位运算优化版：无查表，无分支
static inline char base64_char(uint32_t idx) {
    // idx 范围 0~63
    // 核心思路：利用字符编码的连续性
    uint32_t a = idx + 'A';
    uint32_t b = idx - 26 + 'a';
    uint32_t c = idx - 52 + '0';
    uint32_t d = '+' + ((idx - 62) & 0);  // 这个技巧后面解释
    
    // 用掩码选择正确的区间
    uint32_t mask1 = ((idx - 26) >> 8) & 0xFF;  // idx < 26 时全1
    uint32_t mask2 = ((idx - 52) >> 8) & 0xFF;  // idx < 52 时全1
    uint32_t mask3 = ((idx - 62) >> 8) & 0xFF;  // idx < 62 时全1
    
    uint32_t result = a;
    result = (mask1 & result) | (~mask1 & b);
    result = (mask2 & result) | (~mask2 & c);
    result = (mask3 & result) | (~mask3 & d);
    
    return (char)result;
}

等等，上面的代码有个问题——d的计算是错的。我故意留了个坑，咱们来填上。

真正的无分支实现

我在项目中遇到过类似的需求，当时需要在一个没有硬件除法器的MCU上做Base64编码。我最终用了这个方案：

// 真正的无分支位运算实现
static inline char base64_char_no_branch(uint32_t idx) {
    // 先处理 0~25 和 26~51 的连续区间
    uint32_t ch = idx + 'A';
    uint32_t adjust = 0;
    
    // 如果 idx >= 26，需要调整到小写字母区间
    adjust = ((idx - 26) >> 8) & 0xFF;  // idx < 26 时 adjust=0xFF
    ch += adjust & ('a' - 'A' - 26);     // 调整量 = 6
    
    // 如果 idx >= 52，调整到数字区间
    adjust = ((idx - 52) >> 8) & 0xFF;  // idx < 52 时 adjust=0xFF
    ch += adjust & ('0' - 'a' - 26);     // 调整量 = -75
    
    // 处理 idx=62 和 idx=63
    // 这里用一个小技巧：62 和 63 的二进制是 0x3E 和 0x3F
    // 它们的低2位不同，可以用来区分
    uint32_t is_62 = ((idx ^ 62) - 1) >> 8;  // idx==62 时全1
    uint32_t is_63 = ((idx ^ 63) - 1) >> 8;  // idx==63 时全1
    
    ch = (is_62 & '+') | (~is_62 & ch);
    ch = (is_63 & '/') | (~is_63 & ch);
    
    return (char)(ch & 0xFF);
}

这段代码看起来有点绕，但核心思想就一句话：用算术右移和掩码来模拟条件选择。当 idx < 26 时，(idx - 26) >> 8 的结果是0xFF（因为负数右移补1），否则是0x00。这个0xFF/0x00就可以当作掩码来用。

性能对比与实测

我曾经在STM32F103（Cortex-M3，72MHz）上做过对比测试，编码1KB的数据：

可以看到，位运算版本快了大约27%，而且不占RAM。但代价是代码体积变大了。对于Flash充裕、RAM紧张的场景，这个取舍是值得的。

SVG流程图：Base64编码的位运算流程

实际项目中的取舍

说实话，并不是所有场景都适合用纯位运算。我个人的建议是：

• 如果RAM非常紧张（比如只有几百字节），用位运算版本，省下查表的那64字节。
• 如果Flash非常紧张，用标准查表法，代码更紧凑。
• 如果两者都还好，用混合法：把最常用的0~51区间用位运算，62和63用查表。这样既快又小。

我曾经在一个项目里，因为用了纯位运算版本，导致代码体积超标，最后不得不改回查表法。嗯，这就是教训——优化不能只看单点性能，要看整体约束。

好了，关于Base64的位运算优化就聊到这里。下一节我们会继续深入位操作的另一个经典应用——CRC校验的快速实现。敬请期待。

公众号:蓝海资料掘金营，微信deep3321