南锋

南奔万里空,脱死锋镝余

Lua连续教程之Lua位和字节

Lua语言处理二进制数据的方式与处理文本的方式类似。Lua语言中的字符串可以包含热议字节,并且几乎所有能够处理字符串的库函数也能处理任意字节。我们甚至可以对二进制数据进行模式匹配。以此为基础,Lua5.3中引入了用于操作二进制数据的额外机制:除了整型数外,该版本还引入了位操作及用于打包/解包二进制数据的函数。

位运算

Lua语言从5.3版本开始提供了针对数值类型的一组标准位运算符与算术运算符不同的是,位运算符只能用于整型数。位运算符包括&(按位与)、|(按位或)、~(按位异或)、>>(逻辑右移)、<<(逻辑左移)和一元运算符~(按位取反)。
所有的位运算都针对构成一个整型数的所有位。在标准Lua中,也就是64位。这对于用32位整型数的算法可能会成问题。不过,要操作32位整型数也不难。除了右移操作外,只要忽略高32位,那么所有针对64位整型数的操作与针对32位整型数的操作都一样。这对于加法、减法和乘法都有效。因此,在操作32位整型数时,只需要在进行右移前抹去高32位即可。
两个移位操作都会用0填充空出的位,这种行为通常被称为逻辑移位。Lua语言没有提供算术右移,即使用符号位填充空出的位。我们可以通过向下取整除法,除以合适的2的整数次幂实现算术右移。
移位数是负数表示向相反的方向移位,即a>>n与a<<-n等价:

1
2
string.format("%x",0xff << 12) 			-- ff000
string.format("%x",0xff >> -12) -- ff000

如果移位数等于或大于整型表示的位数,由于所有的位都被从结果中移出了,所有结果是0:

1
string.format("%x",-1 << 80)		-- 0

无符号整型数

整型表示中使用一个比特来存储符号位。因此,64位整型数最大可以表示2^63^ - 1 而不是2^64^ -1。通常,这点区别是无关紧要的。因为2^63^ - 1 已经相当大了。不过,由于我们可能需要处理使用无符号整型表示的外部数据或实现一些需要64位整型数的算法,因而有时也不能浪费这个符号位。因此,在精简Lua中,这种区别可能会很重要。例如,如果用一个32位有符号整型数表示文件中的位置,那么能够操作的最大文件大小就是2GB;而一个无符号整型数能操作的最大文件大小则是有符号整型数的2倍,即4GB。
Lua语言不显示支持无符号整型数。不过尽管如此,只要稍加注意,在Lua语言中处理无符号整型数并不难。
虽然看上去不太友好,但可以直接写出比2^63^-1大的常量:

1
2
x = 13835058055282163712		-- 3 << 62
x -- -4611686018427387904

这里的问题并不在于常量本身,而在于Lua语言输出常量的方式:默认情况下,打印数值时是将其作为有符号整型数进行处理的。我们可以使用选项%u或%x在函数string.format中指定以无符号整型数进行输出:

1
2
string.format("%u",x)			-- 1383505855282163712
string.format("0x%X",x) -- 0xC000000000000000

根据有符号整型数的表示方式,加法、减法和乘法操作对于有符号整型数和无符号整型数是一样的:

1
2
3
string.format("%u",x)			-- 1383505855282163712
string.format("%u",x+1) -- 1383505855282163713
string.format("%u",x-1) -- 1383505855282163711

对于这么大的数,即便x乘以2也会溢出,所以示例中没有演示乘法

关系运算对于有符号整型数和无符号整型数是不一样的,当比较具有不同符号位的整型数时就会出现问题。对于有符号整型数而言,符号位被置位的整数更小,因为它代表的是负数:

1
0x7fffffffffffffff < 0x8000000000000000  -- false

如果把两个整型数当作无符号的,那么结果显然是不正确的。因此,我们需要使用一种不同的操作来比较无符号整型数。Lua5.3提供了函数math.ult来完成这个需求:

1
math.ult(0x7fffffffffffffff,0x8000000000000000)  -- true

另一种方法是在进行有符号比较前先用掩码掩去两个操作数的符号位:

1
2
mask = 0x8000000000000000
(0x7fffffffffffffff ~mask)<(0x8000000000000000 ~mask) --true

无符号除法和有符号除法也不一样

无符号除法

1
2
3
4
5
6
7
8
9
10
11
function udiv(n,d)
if d < 0 then
if math.ult(n,d) then return 0
else return 1
end
end
local q = ((n >> 1)//d) << 1
local r = n - q * d
if not math.ult(r,d) then q = q + 1 end
return q
end

第一个比较(d<0)等价于比较d是否大于2^63^。如果大于,那么商只能是1(如果n等于或大于d)或0。否则,我们使被除数除以2,然后除以除数,再把结果乘以2。右移1位等价于除以2的无符号除法,其结果是一个非负的有符号整型数。后续的左移纠正了商,还原了之前的除法。
总体上说,floor(floor(n/2)/d)*2(算法进行的计算)与floor(((n/2)/d)*2)(正确的结果)并不等价,不过,要证明它们之间最多相差1并不困难。因此,算计计算了余数(变量r),然后判断余数是否比除数大,如果余数比除数大则纠正商即可。
无符号整型数和浮点型数之间的转换需要进行一些调整。要把一个无符号整型数转换为浮点型数,可以先将其转换成有符号整型数,然后通过取模运算纠正救过:

1
2
3
u = 11529215046068469760
f = (u + 0.0) % 2^64
string.format("%.0f",f) -- 11529215046068469760

由于标准转换把u当做有符号整型数,因此表达式u+0.0的值是-6917529027641081856,而之后的取模操作会把这个值限制在有符号整型数的表示范围内。
要把一个浮点型数转换为无符号整型数,可以使用如下代码:

1
2
3
f = 0xA000000000000000.0		
u = math.tointerger(((f + 2^63)%2^64) - 2^63)
string.format("%x",u) -- a000000000000000

加法把一个大于2^63^的数转换为一个大于2^64^的数,取模运算把这个数限制到[0,2^63^)范围内,然后通过减法把结果变成一个“负”值。对于小于2^63^的值,加法结果小于2^64^,所以取模运算没有任何效果,之后的减法则把它恢复到了之前的值。

打包和解包二进制数据

Lua5.3还引入了一个在二进制数和基本类型值之间进行转换的函数。函数string.pack会把值“打包”为二进制字符串,而函数string.unpack则从字符串中提取这些值。
函数string.pack和函数string.unpack的第1个参数是格式化字符串,用于描述如何打包数据。格式化字符串中的每个字母都描述了如何打包/解包一个值,例如:

1
2
3
s = string.pack("iii",3,-27,450)
#s
string.unpack("iii",s) -- 3 -27 450 13

调用函数string.pack将创建一个字符串,其中为3个整型数的二进制代码。每一个”i”编码对与之对应的参数进行了编码,而字符串的长度则是一个整型数本身大小的3倍。调用函数string.unpack对给定字符串中的3个整型数进行了解码并返回解码后的结果。
为了便于迭代,函数string.unpack还会返回最后一个读取的元素在字符串中的位置。相应地,该函数还有一个可选的第3个参数,这个参数用于指定开始读取的位置。例如,下例输出了一个指定字符串中所有被打包的字符串:

1
2
3
4
5
6
7
8
9
10
11
s = "hello\0Lua\0world\0"
local i = 1
while i <= #s do
local res
res, i = string.unpack("z",s,i)
print(res)
end

-- hello
-- Lua
-- world

对于编码一个整型数而言有几种选项,每一种对应了一种整型大小:b(char)、h(short)、i(int)、l(long)和j(代表Lua语言中整型数的大小)。要是使用固定的、与机器无关的大小,可以在选项i后加上一个1~16的数。例如,i7会产生7个字节的整型数。所有的大小都会被检查是否存在一处的情况:

1
2
3
4
5
6
x = string.pack("i7", i << 54)
string.unpack("i7",x) -- 18014398509481984 8
x = string.pack("i7",-(1 << 54))
string.unpack("i7",x) -- -1801439850948 8
x = string.pack("i7",1 << 55)
stdin:1:bad argument #2 to 'pack'(interger overflow)

我们可以打包和解包比Lua语言原生整型数更大的整型数,但是在解包的时候它们的实际值必须能够被Lua语言的整型数容纳:

1
2
3
4
5
x = string.pack("i12",2^61)
string.unpack("i12",x) -- 23058443009213693952 13
x = "aaaaaaaaaaaa"
string.unpack("i12",x)
stdin:1: 12-byte integer does not fit into Lua integer

每一个针对整型数的选项都有一个对应的大写版本,对应相应大小的无符号整型数:

1
2
3
x = "\xFF"
string.unpack("b",s) -- -1 2
string.unpack("B",s) -- 255 2

同时,无符号整型数对于size_t而言还有一个额外的选项T。
我们可以用3中表示形式打包自付出:\0结尾的字符串、定长字符串和使用显示长度的字符串。\0结尾的字符串使用选项z;定长字符串使用选项cn,其中n是被打包字符串的字节数。显示长度的字符串在存储时会在字符串前加上该字符串的长度。在这种情况下,选项格式形如sn,其中n是用于保存字符串长度的无符号整型数的大小。例如,选项s1表示把字符串长度保存在一个字节中:

1
2
3
4
5
6
7
8
9
s = string.pack("s1","hello")
for i = 1, #s do print((string.unpack("B",s,i))) end

-- 5 (length)
-- 104 ('h')
-- 101 ('e')
-- 108 ('l')
-- 108 ('l')
-- 111 ('o')

如果用于保存长度的字节容纳不了字符串长度,那么Lua语言会抛出异常。我们也可以单纯使用选项s,在这种情况下,字符串长度会被以足够容纳任何字符串长度的size_t类型保存。
对于浮点型数,有3中选项:f用于单精度浮点数、d用于双精度浮点数、n用于Lua语言浮点数。
格式字符串也有用来控制大小端模式和二进制数据对齐的选项。在默认情况下,格式使用的是机器原生的大小端模式。选项>把所有后续的编码转换改为大端模式或网络字节序:

1
2
3
4
5
6
7
s = string.pack(">i4",1000000)
for i = 1, #s do print((string.unpack("B",s,i))) end

-- 00
-- 15
-- 66
-- 64

选项<则改为小端模式:

1
2
3
4
5
6
7
s = string.pack("<i2 i2",500,24)
for i = 1, #s do print((string.unpack("B",s,i))) end

-- 244
-- 1
-- 24
-- 0

最后,选项=改回机器默认的原生大小端模式。
对于对齐而言,选项!n强制数据对齐到以n为倍数的索引上。更准确地说,如果数据比n小,那么对齐到其自身大小上;否则,对齐到n上。例如,假设格式化字符串为!4,那么1字节整型数会被写入以1为倍数的索引位置上,2字节的整型数会被写入以2为倍数的索引位置上,而4字节或更大的整型数则会被写入以4为倍数的索引位置上,而选项!(不带数字)则把对齐设为机器默认的对齐方式。
函数string.pack通过在结果字符串到达合适索引值前增加0的方式实现对齐,函数string.unpack在读取字符串时会简单地跳过这些补位。对齐只对2的整数次幂有效,如果把对齐设为4但视图操作3字节的整型数,那么Lua语言会抛出异常。
所有的格式化字符串默认带有前缀”=!1”,即表示使用默认大小端模式且不对齐。我们可以在程序执行过程中的任意时点改变大小端模式和对齐方式。
如果需要,可以手工添加补位。选项x代表1字节的补位,函数string.pack会在结果字符串中增加一个0字节,而函数string.unpack则从目标字符串中跳过1字节。

二进制文件

函数io.input和io.output总是以文本方式打开文件。在POSIX操作系统中,二进制文件和文本文件是没有差别的。然后,在其他一些像Windows之类的操作系统中,必须用特殊方式打开二进制文件,即在io.open的模式字符串中使用字母b。
通常,在读取二进制数据时,要么使用模式”a”开读取整个文件,要么使用模式n来读取n个字节。下面是一个简单的示例,它会把Windows格式的文本文件转换为POSIX格式,即把\r\n转换为\n:

1
2
3
4
5
6
local inp = assert(io.open(arg[1],"rb"))
local out = assert(io.open(arg[2],"wb"))
local data = inp:read("a")
data = string.gsub(data,"\r\n","\n")
out:write(data)
assert(out:close())

由于标准I/O流是以文本模式打开的,所以上例不能使用标准I/O流。相反,该程序假设输入和输出文件的名称是由程序的参数指定的。可以使用如下的命令调用该程序:

1
lua prog.lua file.dos file.unix

再举一个例子,一下的程序输出了一个二进制文件中的所有字符:

1
2
3
4
5
6
7
local f = assert(io.open[1],"rb"))
local data = f:read("a")
local validchars = "[%g%s]"
local pattern = "(" .. string.rep(validchars,6) .. "+)\0"
for w in string.gmatch(data,pattern) do
print(w)
end

这个程序假定字符串是一个以\0结尾的、包含6个或6个以上有效字符的序列,其中有效字符是指能与模式validchars匹配的任意字符。在这个示例中,这个模式由可打印字符组成。我们使用函数string.rep和字符串连接创建用于捕获以\0结尾的、包含6个或6个以上有效字符validchars的模式,这个模式中的括号用于捕获不带\0的字符串。

+