lua-bit.txt (17022B)
1 *lua-bit.txt* Nvim 2 *lua-bit* 3 4 LUA BITOP REFERENCE MANUAL 5 6 7 Adapted from <https://bitop.luajit.org> 8 9 10 Lua BitOp is a C extension module for Lua 5.1/5.2 which adds bitwise 11 operations on numbers. 12 13 Type |gO| to see the table of contents. 14 15 ============================================================================== 16 API FUNCTIONS *lua-bit-api* 17 18 This list of API functions is not intended to replace a tutorial. If you are 19 not familiar with the terms used, you may want to study the Wikipedia article 20 on bitwise operations (https://en.wikipedia.org/wiki/Bitwise_operation) first. 21 22 ------------------------------------------------------------------------------ 23 Loading the BitOp module 24 *lua-bit-module* 25 26 The suggested way to use the BitOp module is to add the following to the start 27 of every Lua file that needs one of its functions: >lua 28 local bit = require("bit") 29 < 30 This makes the dependency explicit, limits the scope to the current file and 31 provides faster access to the bit.* functions, too. It's good programming 32 practice not to rely on the global variable bit being set (assuming some other 33 part of your application has already loaded the module). The require function 34 ensures the module is only loaded once, in any case. 35 36 ------------------------------------------------------------------------------ 37 Defining Shortcuts 38 *lua-bit-shortcuts* 39 40 It's a common (but not a required) practice to cache often used module 41 functions in locals. This serves as a shortcut to save some typing and also 42 speeds up resolving them (only relevant if called hundreds of thousands of 43 times). 44 >lua 45 local bnot = bit.bnot 46 local band, bor, bxor = bit.band, bit.bor, bit.bxor 47 local lshift, rshift, rol = bit.lshift, bit.rshift, bit.rol 48 -- etc... 49 50 -- Example use of the shortcuts: 51 local function tr_i(a, b, c, d, x, s) 52 return rol(bxor(c, bor(b, bnot(d))) + a + x, s) + b 53 end 54 < 55 56 Remember that `and`, `or` and `not` are reserved keywords in Lua. They cannot 57 be used for variable names or literal field names. That's why the 58 corresponding bitwise functions have been named `band`, `bor`, and `bnot` (and 59 `bxor` for consistency). 60 61 While we are at it: a common pitfall is to use bit as the name of a local 62 temporary variable — well, don't! :-) 63 64 ------------------------------------------------------------------------------ 65 About the Examples 66 67 The examples below show small Lua one-liners. Their expected output is shown 68 after `-->`. This is interpreted as a comment marker by Lua so you can cut & 69 paste the whole line to a Lua prompt and experiment with it. 70 71 Note that all bit operations return signed 32 bit numbers (rationale). And 72 these print as signed decimal numbers by default. 73 74 For clarity the examples assume the definition of a helper function 75 `printx()`. This prints its argument as an unsigned 32 bit hexadecimal number 76 on all platforms: 77 >lua 78 function printx(x) 79 print("0x"..bit.tohex(x)) 80 end 81 < 82 ------------------------------------------------------------------------------ 83 Bit operations 84 *lua-bitop* 85 86 y = bit.tobit(x) *bit.tobit()* 87 Normalizes a number to the numeric range for bit operations and returns 88 it. This function is usually not needed since all bit operations already 89 normalize all of their input arguments. See |lua-bit-semantics|. 90 91 Example: >lua 92 print(0xffffffff) --> 4294967295 (see Note) 93 print(bit.tobit(0xffffffff)) --> -1 94 printx(bit.tobit(0xffffffff)) --> 0xffffffff 95 print(bit.tobit(0xffffffff + 1)) --> 0 96 print(bit.tobit(2^40 + 1234)) --> 1234 97 < 98 Note: |lua-bit-hex-literals| explains why the numbers printed in the first 99 two lines differ (if your Lua installation uses a double number type). 100 101 y = bit.tohex(x [,n]) *bit.tohex()* 102 Converts its first argument to a hex string. The number of hex digits is 103 given by the absolute value of the optional second argument. Positive 104 numbers between 1 and 8 generate lowercase hex digits. Negative numbers 105 generate uppercase hex digits. Only the least-significant `4*|n|` bits are 106 used. The default is to generate 8 lowercase hex digits. 107 108 Example: >lua 109 print(bit.tohex(1)) --> 00000001 110 print(bit.tohex(-1)) --> ffffffff 111 print(bit.tohex(0xffffffff)) --> ffffffff 112 print(bit.tohex(-1, -8)) --> FFFFFFFF 113 print(bit.tohex(0x21, 4)) --> 0021 114 print(bit.tohex(0x87654321, 4)) --> 4321 115 < 116 y = bit.bnot(x) *bit.bnot()* 117 Returns the bitwise `not` of its argument. 118 119 Example: >lua 120 print(bit.bnot(0)) --> -1 121 printx(bit.bnot(0)) --> 0xffffffff 122 print(bit.bnot(-1)) --> 0 123 print(bit.bnot(0xffffffff)) --> 0 124 printx(bit.bnot(0x12345678)) --> 0xedcba987 125 < 126 y = bit.bor(x1 [,x2...]) *bit.bor()* 127 y = bit.band(x1 [,x2...]) *bit.band()* 128 y = bit.bxor(x1 [,x2...]) *bit.bxor()* 129 Returns either the bitwise `or`, bitwise `and`, or bitwise `xor` of all of its 130 arguments. Note that more than two arguments are allowed. 131 132 Example: >lua 133 print(bit.bor(1, 2, 4, 8)) --> 15 134 printx(bit.band(0x12345678, 0xff)) --> 0x00000078 135 printx(bit.bxor(0xa5a5f0f0, 0xaa55ff00)) --> 0x0ff00ff0 136 < 137 y = bit.lshift(x, n) *bit.lshift()* 138 y = bit.rshift(x, n) *bit.rshift()* 139 y = bit.arshift(x, n) *bit.arshift()* 140 Returns either the bitwise `logical left-shift`, bitwise `logical` 141 `right-shift`, or bitwise `arithmetic right-shift` of its first argument 142 by the number of bits given by the second argument. 143 144 Logical shifts treat the first argument as an unsigned number and shift in 145 0-bits. Arithmetic right-shift treats the most-significant bit as a sign 146 bit and replicates it. Only the lower 5 bits of the shift count are used 147 (reduces to the range [0..31]). 148 149 Example: >lua 150 print(bit.lshift(1, 0)) --> 1 151 print(bit.lshift(1, 8)) --> 256 152 print(bit.lshift(1, 40)) --> 256 153 print(bit.rshift(256, 8)) --> 1 154 print(bit.rshift(-256, 8)) --> 16777215 155 print(bit.arshift(256, 8)) --> 1 156 print(bit.arshift(-256, 8)) --> -1 157 printx(bit.lshift(0x87654321, 12)) --> 0x54321000 158 printx(bit.rshift(0x87654321, 12)) --> 0x00087654 159 printx(bit.arshift(0x87654321, 12)) --> 0xfff87654 160 < 161 y = bit.rol(x, n) *bit.rol()* 162 y = bit.ror(x, n) *bit.ror()* 163 Returns either the bitwise `left rotation`, or bitwise `right rotation` of its 164 first argument by the number of bits given by the second argument. Bits 165 shifted out on one side are shifted back in on the other side. 166 167 Only the lower 5 bits of the rotate count are used (reduces to the range 168 [0..31]). 169 170 Example: >lua 171 printx(bit.rol(0x12345678, 12)) --> 0x45678123 172 printx(bit.ror(0x12345678, 12)) --> 0x67812345 173 < 174 y = bit.bswap(x) 175 Swaps the bytes of its argument and returns it. This can be used to 176 convert little-endian 32 bit numbers to big-endian 32 bit numbers or vice 177 versa. 178 179 Example: >lua 180 printx(bit.bswap(0x12345678)) --> 0x78563412 181 printx(bit.bswap(0x78563412)) --> 0x12345678 182 < 183 ------------------------------------------------------------------------------ 184 Example Program 185 186 This is an implementation of the (naïve) Sieve of Eratosthenes algorithm. It 187 counts the number of primes up to some maximum number. 188 189 A Lua table is used to hold a bit-vector. Every array index has 32 bits of the 190 vector. Bitwise operations are used to access and modify them. Note that the 191 shift counts don't need to be masked since this is already done by the BitOp 192 shift and rotate functions. 193 >lua 194 local bit = require("bit") 195 local band, bxor = bit.band, bit.bxor 196 local rshift, rol = bit.rshift, bit.rol 197 198 local m = tonumber(arg and arg[1]) or 100000 199 if m < 2 then m = 2 end 200 local count = 0 201 local p = {} 202 203 for i=0,(m+31)/32 do p[i] = -1 end 204 205 for i=2,m do 206 if band(rshift(p[rshift(i, 5)], i), 1) ~= 0 then 207 count = count + 1 208 for j=i+i,m,i do 209 local jx = rshift(j, 5) 210 p[jx] = band(p[jx], rol(-2, j)) 211 end 212 end 213 end 214 215 io.write(string.format("Found %d primes up to %d\n", count, m)) 216 < 217 Lua BitOp is quite fast. This program runs in less than 90 milliseconds on a 3 218 GHz CPU with a standard Lua installation, but performs more than a million 219 calls to bitwise functions. If you're looking for even more speed, check out 220 |lua-luajit|. 221 222 ------------------------------------------------------------------------------ 223 Caveats *lua-bit-caveats* 224 225 Signed Results ~ 226 227 Returning signed numbers from bitwise operations may be surprising to 228 programmers coming from other programming languages which have both signed and 229 unsigned types. But as long as you treat the results of bitwise operations 230 uniformly everywhere, this shouldn't cause any problems. 231 232 Preferably format results with `bit.tohex` if you want a reliable unsigned 233 string representation. Avoid the `"%x"` or `"%u"` formats for `string.format`. They 234 fail on some architectures for negative numbers and can return more than 8 hex 235 digits on others. 236 237 You may also want to avoid the default number to string coercion, since this 238 is a signed conversion. The coercion is used for string concatenation and all 239 standard library functions which accept string arguments (such as `print()` or 240 `io.write()`). 241 242 Conditionals ~ 243 244 If you're transcribing some code from C/C++, watch out for bit operations in 245 conditionals. In C/C++ any non-zero value is implicitly considered as `true`. 246 E.g. this C code: >c 247 if (x & 3) ... 248 < 249 must not be turned into this Lua code: >lua 250 if band(x, 3) then ... -- wrong! 251 < 252 In Lua all objects except `nil` and `false` are considered `true`. This 253 includes all numbers. An explicit comparison against zero is required in this 254 case: >lua 255 if band(x, 3) ~= 0 then ... -- correct! 256 257 Comparing Against Hex Literals ~ 258 259 Comparing the results of bitwise operations (signed numbers) against hex 260 literals (unsigned numbers) needs some additional care. The following 261 conditional expression may or may not work right, depending on the platform 262 you run it on: >lua 263 bit.bor(x, 1) == 0xffffffff 264 < 265 E.g. it's never true on a Lua installation with the default number type. Some 266 simple solutions: 267 268 Never use hex literals larger than 0x7fffffff in comparisons: >lua 269 bit.bor(x, 1) == -1 270 < 271 Or convert them with bit.tobit() before comparing: >lua 272 bit.bor(x, 1) == bit.tobit(0xffffffff) 273 < 274 Or use a generic workaround with bit.bxor(): >lua 275 bit.bxor(bit.bor(x, 1), 0xffffffff) == 0 276 < 277 Or use a case-specific workaround: >lua 278 bit.rshift(x, 1) == 0x7fffffff 279 < 280 ============================================================================== 281 OPERATIONAL SEMANTICS AND RATIONALE *lua-bit-semantics* 282 283 284 Input and Output Ranges ~ 285 *lua-bit-io-ranges* 286 287 Bitwise operations cannot sensibly be applied to FP numbers (or their 288 underlying bit patterns). They must be converted to integers before operating 289 on them and then back to FP numbers. 290 291 It's desirable to define semantics that work the same across all platforms. 292 This dictates that all operations are based on the common denominator of 32 293 bit integers. The `float` type provides only 24 bits of precision. This makes it 294 unsuitable for use in bitwise operations. Lua BitOp refuses to compile against 295 a Lua installation with this number type. 296 297 Bit operations only deal with the underlying bit patterns and generally ignore 298 signedness (except for arithmetic right-shift). They are commonly displayed 299 and treated like unsigned numbers, though. 300 301 But the Lua number type must be signed and may be limited to 32 bits. Defining 302 the result type as an unsigned number would not be cross-platform safe. All 303 bit operations are thus defined to return results in the range of signed 32 304 bit numbers (converted to the Lua number type). 305 306 *lua-bit-hex-literals* 307 Hexadecimal literals are treated as unsigned numbers by the Lua parser before 308 converting them to the Lua number type. This means they can be out of the 309 range of signed 32 bit integers if the Lua number type has a greater range. 310 E.g. 0xffffffff has a value of 4294967295 in the default installation, but may 311 be -1 on embedded systems. It's highly desirable that hex literals are treated 312 uniformly across systems when used in bitwise operations. All bit operations 313 accept arguments in the signed or the unsigned 32 bit range (and more, see 314 below). Numbers with the same underlying bit pattern are treated the same by 315 all operations. 316 317 318 Modular Arithmetic ~ 319 *lua-bit-modular-arith* 320 321 Arithmetic operations on n-bit integers are usually based on the rules of 322 modular arithmetic modulo 2^n. Numbers wrap around when the mathematical result 323 of operations is outside their defined range. This simplifies hardware 324 implementations and some algorithms actually require this behavior (like many 325 cryptographic functions). 326 327 E.g. for 32 bit integers the following holds: `0xffffffff + 1 = 0` 328 329 Arithmetic modulo 2^32 is trivially available if the Lua number type is a 32 330 bit integer. Otherwise normalization steps must be inserted. Modular 331 arithmetic should work the same across all platforms as far as possible: 332 333 - For the default number type of double, arguments can be in the range of 334 ±2^51 and still be safely normalized across all platforms by taking their 335 least-significant 32 bits. The limit is derived from the way doubles are 336 converted to integers. 337 - The function bit.tobit can be used to explicitly normalize numbers to 338 implement modular addition or subtraction. E.g. >lua 339 bit.tobit(0xffffffff + 1) 340 returns 0 on all platforms. 341 - The limit on the argument range implies that modular multiplication is 342 usually restricted to multiplying already normalized numbers with small 343 constants. FP numbers are limited to 53 bits of precision, anyway. E.g. 344 (2^30+1)^2 does not return an odd number when computed with doubles. 345 346 BTW: The `tr_i` function shown here |lua-bit-shortcuts| is one of the 347 non-linear functions of the (flawed) MD5 cryptographic hash and relies on 348 modular arithmetic for correct operation. The result is fed back to other 349 bitwise operations (not shown) and does not need to be normalized until the 350 last step. 351 352 353 Restricted and undefined behaviors ~ 354 *lua-bit-restrictions* 355 356 The following rules are intended to give a precise and useful definition (for 357 the programmer), yet give the implementation (interpreter and compiler) the 358 maximum flexibility and the freedom to apply advanced optimizations. It's 359 strongly advised not to rely on undefined or implementation-defined behavior. 360 361 - All kinds of floating-point numbers are acceptable to the bitwise 362 operations. None of them cause an error, but some may invoke undefined 363 behavior: 364 - -0 is treated the same as +0 on input and is never returned as a result. 365 - Passing ±Inf, NaN or numbers outside the range of ±2^51 as input yields 366 an undefined result. 367 - Non-integral numbers may be rounded or truncated in an 368 implementation-defined way. This means the result could differ between 369 different BitOp versions, different Lua VMs, on different platforms or 370 even between interpreted vs. compiled code (as in LuaJIT). Avoid 371 passing fractional numbers to bitwise functions. Use `math.floor()` or 372 `math.ceil()` to get defined behavior. 373 - Lua provides auto-coercion of string arguments to numbers by default. This 374 behavior is deprecated for bitwise operations. 375 376 ============================================================================== 377 COPYRIGHT 378 379 Lua BitOp is Copyright (C) 2008-2025 Mike Pall. 380 Lua BitOp is free software, released under the MIT license. 381 382 vim:tw=78:ts=4:sw=4:sts=4:et:ft=help:norl: