cstdio 的源码学习分析 11- 格式化输入输出函数 fprintf---format 解析跳转表逻辑分析
背景
在 stdio.h 的 printf 类型的函数中，要完成变量打印，主要有两个核心任务：一个是识别 format 占位符构造 printf_info 结构体，一个是打印该种特定类型的变量，这个跳转表机制就是为了识别 format 占位符而创建的。
%[flags][width][.precision][length]specifier对于这样的一个字符串类型识别，我们通常会采用自动机的方式进行识别，设定多个状态，每个状态代表一个识别位，状态之间的跳转需要条件，直到最后识别到specifier类型，这时，我们就能够完全解析出所有字段，上面构想的方法其实就是有限状态自动机的方法。
但是，因为 C 标准中规定了上面五个字段中可以有很多种组合，这个状态数量的叠加将是非常巨大的，我们能否寻找到一种比较简单的方式实现这个逻辑呢？
答案是有的，在 C 语言中有一种语法深为人所诟病，那就 goto 语句，可以进行无条件跳转到设定好的标号处，当然大部分情况下我们是不建议使用的，但是它在这种场景下就很契合，试想一下，我们的有限状态自动机中每一个状态是否就是一个标号呢？在这个标号中处理当前符号的识别，处理完成之后，移动到下一个字符，并通过我们设定好的跳转表跳转到下一个标号处进行处理，这个过程中，我们需要维护好的就是这个关键的跳转表，它记录了当前符号的下一个处理标号的位置，跳转表充当了有限状态自动机中触发状态变化函数的作用。
跳转表相关的宏定义/变量
1.jump_table---字符对应的跳转位置，字符在 L_(' ')和 L_('z')之间
其实这些字符的设定规律也比较明显：
跳转值为 0 代表在 format 字符串解析过程中没有特殊含义的字符：如大写的 LMNOPQ 等；
跳转值为 1 代表' '，2 代表'+'，3 代表'-'，4 代表'#'，5 代表'0'，6 代表''，7 代表'*'，9 代表'.'；
跳转值 8 代表数字 1 到 9；
跳转值 10 代表'h'(类型前缀，表示长度扩展信息，如 hd 表示 short int);
跳转值 11 代表'l'(类型前缀，表示长度扩展信息，如 ld 表示 long int);
跳转值 12 代表'L'和'q''(类型前缀，表示长度扩展信息，如 Lf 表示 long long double)
跳转值 13 代表'Z'和'z'，size_t 类型
跳转值 14 代表'%'
跳转值 15 代表'd'和'i'，有符号整型数据
跳转值 16 代表'u'，无符号整型数据
跳转值 17 代表'o'，无符号八进制整型数据
跳转值 18 代表'X'和'x'，无符号 16 进制整型数据
跳转值 19 代表'E', 'e', 'F', 'f', 'G', 'g'，浮点数
跳转值 20 代表'c'，字符类型
跳转值 21 代表's', 'S'，字符串类型
跳转值 22 代表'p'，指针类型
跳转值 23 代表'n'，数字类型
跳转值 24 代表'm'，标准错误类型
跳转值 25 代表'C'，宽字符类型
跳转值 26 代表'A', 'a'，浮点数 16 进制类型
跳转值 27 代表't'，ptrdiff_t 类型
跳转值 28 代表'j'，intmax_t 类型
跳转值 29 代表'I'，标识是否使用额外的字符解释，如在标准字符中使用到了宽字符
跳转值 30 代表'B', 'b'，二进制整型数据
2.NOT_IN_JUMP_RANGE(Ch)---判断字符是否在跳转范围内
因为我们规定可以识别跳转的字符在 L_(' ')和 L_('z')之间，其他字符均视为未知字符
3.CHAR_CLASS(Ch)---获取对应的跳转值
因为 jump_table 是按照 L_(' ')和 L_('z')之间编写的，所以将对应字符值减去 L_(' ')可以得到索引值，进而取出对应的跳转值
4.LABEL(Name)---label 宏
定义 label 的格式，增加 do_前缀
如：LABEL (flag_space):表示do_flag_space:label
5.JUMP_TABLE_TYPE---跳转表中存储的数据类型
6.JUMP_TABLE_BASE_LABEL---基础 label
即 do_form_unknown，未知格式跳转
7.REF(Name)---计算与基础 label 的地址差
C 语言中可以使用 &&符号获取标签名的地址
8.JUMP(ChExpr, table)---根据表与输入字符进行跳转
首先计算当前输入字符的偏移：如果是有效字符，则返回表的对应跳转位置，否则返回 REF (form_unknown)，即 0；
取得要跳转的标号的地址 base+offset；
进行跳转 goto *ptr。
这里其实可以把标号当做函数指针，goto 语句类似函数调用。
核心跳转表定义
以下跳转表都定义在 STEP0_3_TABLE 宏中
1.step0_jumps[31]---开始进行 format 占位符识别或识别到 flags 时使用
仔细看，我们可以看到，这里的顺序与 jump_table 的标号是保持一致的，比如我们前面的例子中 %c，在此处进行跳转时，会直接跳转到 REF (form_character)，针对这样的简单 format，一般在这里就跳转成功了，进行相应的打印。
那么在哪些情况下会使用到这张表呢？通过代码中的分析，可以看到如下几种情况：
因为针对合法字符格式，在这些字符后跟着的应该是 step0_jumps 这样对应的格式，此时识别的就是 flags 相关的字符
format 占位符的一般形式：%[flags][width][.precision][length]specifier
(1).识别了 %符号后的第一个字符
(2).识别空格符之后
(3).识别'+'之后
(4).识别'-'之后
(5).识别'#'之后
(6).识别‘0’之后
(7).识别'''之后
(8).识别'I'之后
2.step1_jumps[31]---识别到 width 相关的字符时使用
注意这个表与 step0_jumps 的对比，我们可以发现，如下字符对应的位置，都被置为了 REF (form_unknown)：
' '，'+'，'-'，'#'，'0'，'''，'I'---因为在 flags 识别中出现了，后续不可能再出现了，如果出现，则认为是异常模式；
'*'，'1'...'9'---是 width 的识别关键字符，识别出现后，将会把相关字符取出，后续如果继续出现，那说明是异常模式
使用表的情况：
(1).识别到'*'之后
(2).识别到'1'...'9'之后
3.step2_jumps[31]---识别到 precision 相关字符时使用
对比 step1_jumps 可以发现，'.' 位置被置为 REF (form_unknown)
(1)识别到'*'后
4.step3a_jumps[31]---识别到第一个'h'修饰符之后使用
对比 step2_jumps 之后发现：
原来'h'的位置从 REF (mod_half)变为 REF (mod_halfhalf)，为了识别'hh'的情况
'l'，'L'，'q'，'z'，'Z'，'E'，'e'，'F'，'f'，'G'，'g'，'c'，'s'，'S'，'p'，'m'，'C'，’a’，'A'，'t'，'j'，都被置为 REF (form_unknown)，因为这些都是非法组合
(1).识别到'h'后
5.step3b_jumps[31]---识别到第一个'l'修饰符之后使用
对比 step2_jumps 之后发现：
原来'l'的位置从 REF (mod_long)变为 REF (mod_longlong)，为了识别'll'的情况
'h'，'L'，'q'，'z'，'Z'，'t'，'j'被置为 REF (form_unknown)，因为这些都是非法组合
(1),识别到'l'之后
以下跳转表都定义在 STEP4_TABLE 宏中
6.step4_jumps[31]---识别具体类型时使用
这里同 step3a_jumps 对比：
'h'位置从 REF (mod_halfhalf)变为 REF (form_unknown)，表明'hh'识别完成
还原了之前不能和'h'组合的类型
同 step3b_jumps 对比：
'l'位置从 REF (mod_longlong)变为 REF (form_unknown)，表明'll'识别完成
还原了之前不能和'l'组合的类型
总的来说，这里就是识别所有可能类型的
(1).识别到'hh'之后
(2).识别到'L'、‘q’、'll'之后
(3).识别到'z'之后
(4).识别到't'之后
(5).识别到'j'之后
(6).识别 specs 中的每一个特定类型时使用
总结
跳转表的核心任务是解析
format 占位符的一般形式：%[flags][width][.precision][length]specifier
通过使用五张跳转表（3a 与 3b 处理两种情况，看做一张），对应识别的五个字段，后一个字段相比前一个字段，可跳转范围减少，对应限制只有合法的组合才能出现，一旦出现异常模式则直接跳转到 REF (form_unknown)。
通过使用跳转表机制，将识别过程进行了拆分，使得逻辑更加清晰，每个阶段每张表任务不同，也不会造成干扰，值得我们学习借鉴。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/44ac3140b3b2d4cc44e96126c】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论