base32.lua at main · push.cx/typeid-lua

push.cx / typeid-lua
Implementation of TypeID in Lua
typeid-lua / base32.lua
at main 6.1 kB view raw
  1-- This is not a general-purpose encoder and decoder for all strings, it only
  2-- works on UUIDs.
  3--
  4-- Ported from https://github.com/jetify-com/typeid-go/blob/5c084b87132053828b438b81e6d36247674c25b0/base32/base32.go
  5local Base32 = {}
  6
  7-- Crockford's Base32 alphabet
  8Base32.ALPHABET = {
  9  [0]= -- index lookup table from 0, not 1
 10  "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
 11  "a", "b", "c", "d", "e", "f", "g", "h", "j", "k",
 12  "m", "n", "p", "q", "r", "s", "t", "v", "w", "x",
 13  "y", "z",
 14}
 15
 16-- encode a length 16 one-byte integer table into a size 26 string
 17function Base32.encode(id)
 18  if #id ~= 16 then
 19    error("invalid id size")
 20  end
 21
 22  local str = {}
 23
 24  -- 10 byte timestamp
 25  str[1]  = Base32.ALPHABET[(id[1] & 224) >> 5]
 26  str[2]  = Base32.ALPHABET[id[1] & 31]
 27  str[3]  = Base32.ALPHABET[(id[2] & 248) >> 3]
 28  str[4]  = Base32.ALPHABET[((id[2] & 7) << 2) | ((id[3] & 192) >> 6)]
 29  str[5]  = Base32.ALPHABET[(id[3] & 62) >> 1]
 30  str[6]  = Base32.ALPHABET[((id[3]&1) << 4) | ((id[4] & 240) >> 4)]
 31  str[7]  = Base32.ALPHABET[((id[4] & 15) << 1) | ((id[5] & 128) >> 7)]
 32  str[8]  = Base32.ALPHABET[(id[5] & 124) >> 2]
 33  str[9]  = Base32.ALPHABET[((id[5] & 3) << 3) | ((id[6] & 224) >> 5)]
 34  str[10] = Base32.ALPHABET[id[6] & 31]
 35
 36  -- 16 bytes of entropy
 37  str[11] = Base32.ALPHABET[(id[7] & 248) >> 3]
 38  str[12] = Base32.ALPHABET[((id[7] & 7) << 2) | ((id[8] & 192) >> 6)]
 39  str[13] = Base32.ALPHABET[(id[8] & 62) >> 1]
 40  str[14] = Base32.ALPHABET[((id[8] & 1) << 4) | ((id[9] & 240) >> 4)]
 41  str[15] = Base32.ALPHABET[((id[9] & 15) << 1) | ((id[10] & 128) >> 7)]
 42  str[16] = Base32.ALPHABET[(id[10] & 124) >> 2]
 43  str[17] = Base32.ALPHABET[((id[10] & 3) << 3) | ((id[11] & 224) >> 5)]
 44  str[18] = Base32.ALPHABET[id[11] & 31]
 45  str[19] = Base32.ALPHABET[(id[12] & 248) >> 3]
 46  str[20] = Base32.ALPHABET[((id[12] & 7) << 2) | ((id[13] & 192) >> 6)]
 47  str[21] = Base32.ALPHABET[(id[13] & 62) >> 1]
 48  str[22] = Base32.ALPHABET[((id[13] & 1) << 4) | ((id[14] & 240) >> 4)]
 49  str[23] = Base32.ALPHABET[((id[14] & 15) << 1) | ((id[15] & 128) >> 7)]
 50  str[24] = Base32.ALPHABET[(id[15] & 124) >> 2]
 51  str[25] = Base32.ALPHABET[((id[15] & 3) << 3) | ((id[16] & 224) >> 5)]
 52  str[26] = Base32.ALPHABET[id[16] & 31]
 53
 54  return table.concat(str)
 55end
 56
 57-- byte -> index lookup table for O(1) lookups when unmarshaling
 58-- 0xFF is a sentinel value for invalid indexes
 59Base32.DEC = {
 60  [0]= -- index lookup table from 0, not 1
 61  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 62  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 63  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 64  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 65  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x01,
 66  0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF,
 67  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 68  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 69  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 70  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C,
 71  0x0D, 0x0E, 0x0F, 0x10, 0x11, 0xFF, 0x12, 0x13, 0xFF, 0x14,
 72  0x15, 0xFF, 0x16, 0x17, 0x18, 0x19, 0x1A, 0xFF, 0x1B, 0x1C,
 73  0x1D, 0x1E, 0x1F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 74  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 75  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 76  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 77  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 78  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 79  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 80  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 81  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 82  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 83  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 84  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 85  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 86  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 87}
 88
 89
 90-- decode a length 26 string into a size 16 byte table
 91function Base32.decode(str)
 92  if #str ~= 26 then
 93    error("invalid length")
 94  end
 95
 96  local bytes = {string.byte(str, 1, -1)}
 97
 98  -- Check for invalid characters
 99  for i = 1, #bytes do
100    if Base32.DEC[bytes[i]] == 0xFF then
101      error(string.format("invalid base32 character at position %s: %s", i, bytes[i]))
102    end
103  end
104
105  local id = {}
106
107  -- the original go wraps, we & 0xFF, equivalent to % 256
108
109  -- 48 bits/6 bytes timestamp
110  id[1]  = ((Base32.DEC[bytes[1]] << 5) | Base32.DEC[bytes[2]]) & 0xFF
111  id[2]  = ((Base32.DEC[bytes[3]] << 3) | (Base32.DEC[bytes[4]] >> 2)) & 0xFF
112  id[3]  = ((Base32.DEC[bytes[4]] << 6) | (Base32.DEC[bytes[5]] << 1) | (Base32.DEC[bytes[6]] >> 4)) & 0xFF
113  id[4]  = ((Base32.DEC[bytes[6]] << 4) | (Base32.DEC[bytes[7]] >> 1)) & 0xFF
114  id[5]  = ((Base32.DEC[bytes[7]] << 7) | (Base32.DEC[bytes[8]] << 2) | (Base32.DEC[bytes[9]] >> 3)) & 0xFF
115  id[6]  = ((Base32.DEC[bytes[9]] << 5) | Base32.DEC[bytes[10]]) & 0xFF
116
117  -- 80 bits/10 bytes of entropy
118  id[7]  = ((Base32.DEC[bytes[11]] << 3) | (Base32.DEC[bytes[12]] >> 2)) & 0xFF-- First 4 bits are the version
119  id[8]  = ((Base32.DEC[bytes[12]] << 6) | (Base32.DEC[bytes[13]] << 1) | (Base32.DEC[bytes[14]] >> 4)) & 0xFF
120  id[9]  = ((Base32.DEC[bytes[14]] << 4) | (Base32.DEC[bytes[15]] >> 1)) & 0xFF -- First 2 bits are the bytesariant
121  id[10] = ((Base32.DEC[bytes[15]] << 7) | (Base32.DEC[bytes[16]] << 2) | (Base32.DEC[bytes[17]] >> 3)) & 0xFF
122  id[11] = ((Base32.DEC[bytes[17]] << 5) | Base32.DEC[bytes[18]]) & 0xFF
123  id[12] = ((Base32.DEC[bytes[19]] << 3) | (Base32.DEC[bytes[20]] >> 2)) & 0xFF
124  id[13] = ((Base32.DEC[bytes[20]] << 6) | (Base32.DEC[bytes[21]] << 1) | (Base32.DEC[bytes[22]] >> 4)) & 0xFF
125  id[14] = ((Base32.DEC[bytes[22]] << 4) | (Base32.DEC[bytes[23]] >> 1)) & 0xFF
126  id[15] = ((Base32.DEC[bytes[23]] << 7) | (Base32.DEC[bytes[24]] << 2) | (Base32.DEC[bytes[25]] >> 3)) & 0xFF
127  id[16] = ((Base32.DEC[bytes[25]] << 5) | Base32.DEC[bytes[26]]) & 0xFF
128
129  return id
130end
131
132return Base32