Луевости

Решил выложить пару накатанных от нефиг делать модульков на Lua. Из разряда «что на луа писать не стоит». Написано под Lua 5.1.

Декомпрессор NRV2E, практически 1 в 1 переведенный с С. Это один из алгоритмов Оберхеймеровской библиотечки UCL, известен тем, что используется в UPX. Приличное сжатие (обычно лучше, чем у zlib, автор утверждает, что сравнимо с bzip2) и весьма шустрая распаковка (при реализации на ассемблере достигается скорость порядка 25% от memcpy). Легко адаптировать в декомпрессор NRV2B/NRV2D (они отличаются более простым кодированием матч-пар).

-- Error codes
UCL_E = {OK = 0; ERROR = -1; INPUT_OVERRUN = -201; OUTPUT_OVERRUN = -202; LOOKBEHIND_OVERRUN = -203; EOF_NOT_FOUND = -204; INPUT_NOT_CONSUMED = -205; OVERLAP_OVERRUN = -206}

-- Decompress NRV2E block
-- src: compressed block
-- oend: uncompressed block length, optional
function nrv2e_decompress(src, oend)

  local dst = {
    [1] = "";
    pos = 0;
    itemlen = 512;
    
    add = function(self, c)
      if #self[#self] >= self.itemlen then
        table.insert(self, "")
      end
      self[#self] = self[#self] .. c
    end;    
    
    get = function(self)
      local res = string.char(self[math.floor(self.pos / self.itemlen) + 1]:byte(self.pos % self.itemlen + 1))
      self.pos = self.pos + 1
      return res
    end;    
    
    len = function(self)
      return (#self - 1) * self.itemlen + #self[#self]
    end;
    
    tostr = function(self)
      return table.concat(self)
    end;
  }

  if not ((type(src) == "string") and (#src > 0)) then
    return UCL_E.ERROR
  end
  
  local bb = 0
  local ilen, last_m_off = 0, 1
  local inv = {[0] = 1; [1] = 0}
 
  local function getbyte()
    ilen = ilen + 1
    return src:byte(ilen)
  end
  
  local function getbit()
    if bb % 128 == 0 then
      bb = getbyte() * 2 + 1
    else
      bb = bb * 2
    end
    return math.floor((bb % 512) / 256)
  end
  
  while true do
  
    local m_len, m_off
    
    while getbit() > 0 do
      if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst:tostr() end
      if (oend > 0) and (dst:len() >= oend) then return UCL_E.OUTPUT_OVERRUN, dst:tostr() end
      dst:add(string.char(getbyte()))
    end
    
    m_off = 1
    
    while true do
      m_off = 2 * m_off + getbit()
      if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst:tostr() end
      if m_off > (0xFFFFFF + 3) then return UCL_E.LOOKBEHIND_OVERRUN, dst:tostr() end
      if getbit() > 0 then break end
      m_off = 2 * (m_off - 1) + getbit()
    end
    
    if m_off == 2 then
      m_off = last_m_off
      m_len = getbit()
    else
      if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst:tostr() end
      m_off = 256 * (m_off - 3) + getbyte()
      if m_off == 0xFFFFFFFF then break end
      m_len = inv[m_off % 2]
      m_off = math.floor(m_off / 2) + 1
      last_m_off = m_off
    end
    
    if m_len > 0 then
      m_len = 1 + getbit()
    else
      if getbit() > 0 then
        m_len = 3 + getbit()
      else
        m_len = 1
        repeat
          m_len = 2 * m_len + getbit()
          if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst:tostr() end
          if (oend > 0) and (m_len >= oend) then return UCL_E.OUTPUT_OVERRUN, dst:tostr() end
        until getbit() > 0
        m_len = m_len + 3
      end
    end
    
    if m_off > 0x500 then m_len = m_len + 1 end
    if (oend > 0) and ((m_len + dst:len()) >= oend) then return UCL_E.OUTPUT_OVERRUN, dst:tostr() end
    if m_off > dst:len() then return UCL_E.LOOKBEHIND_OVERRUN, dst:tostr() end
    
    dst.pos = dst:len() - m_off
    for i = 0, m_len do
      dst:add(dst:get())
    end
  
  end

  if ilen == #src then
    return UCL_E.OK, dst:tostr()
  elseif ilen < #src then
    return UCL_E.INPUT_NOT_CONSUMED, dst:tostr()
  else
    return UCL_E.INPUT_OVERRUN, dst:tostr()
  end

end

Более ранний вариант. Ближе к оригиналу, но производительность очень быстро падает с ростом размера блока данных (несколько килобайт распакует сравнимо с предыдущим, тестовый же вектор на 2.5 метра распаковывало 6 часов — пока мне не надоело, тогда как оптимизированная версия прожевала за 0.3с).

UCL_E = {OK = 0; ERROR = -1; INPUT_OVERRUN = -201; OUTPUT_OVERRUN = -202; LOOKBEHIND_OVERRUN = -203; EOF_NOT_FOUND = -204; INPUT_NOT_CONSUMED = -205; OVERLAP_OVERRUN = -206}

function nrv2e_decompress(src, oend)

  if not ((type(src) == "string") and (#src > 0)) then
    return UCL_E.ERROR
  end
  
  local bb = 0
  local ilen, last_m_off = 0, 1
  local dst = ""
  local inv = {[0] = 1; [1] = 0}
 
  local function getbyte()
    ilen = ilen + 1
    return src:byte(ilen)
  end
  
  local function getbit()
    if bb % 128 == 0 then
      bb = getbyte() * 2 + 1
    else
      bb = bb * 2
    end
    return math.floor((bb % 512) / 256)
  end
  
  while true do
  
    local m_len, m_off
    
    while getbit() > 0 do
      if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst end
      if (oend > 0) and (#dst >= oend) then return UCL_E.OUTPUT_OVERRUN, dst end
      dst = dst .. string.char(getbyte())
    end
    
    m_off = 1
    
    while true do
      m_off = 2 * m_off + getbit()
      if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst end
      if m_off > (0xFFFFFF + 3) then return UCL_E.LOOKBEHIND_OVERRUN, dst end
      if getbit() > 0 then break end
      m_off = 2 * (m_off - 1) + getbit()
    end
    
    if m_off == 2 then
      m_off = last_m_off
      m_len = getbit()
    else
      if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst end
      m_off = 256 * (m_off - 3) + getbyte()
      if m_off == 0xFFFFFFFF then break end
      m_len = inv[m_off % 2]
      m_off = math.floor(m_off / 2) + 1
      last_m_off = m_off
    end
    
    if m_len > 0 then
      m_len = 1 + getbit()
    else
      if getbit() > 0 then
        m_len = 3 + getbit()
      else
        m_len = 1
        repeat
          m_len = 2 * m_len + getbit()
          if ilen >= #src then return UCL_E.INPUT_OVERRUN, dst end
          if (oend > 0) and (m_len >= oend) then return UCL_E.OUTPUT_OVERRUN, dst end
        until getbit() > 0
        m_len = m_len + 3
      end
    end
    
    if m_off > 0x500 then m_len = m_len + 1 end
    if (oend > 0) and ((m_len + #dst) >= oend) then return UCL_E.OUTPUT_OVERRUN, dst end
    if m_off > #dst then return UCL_E.LOOKBEHIND_OVERRUN, dst end
    
    local m_pos = #dst - m_off
    for i = 0, m_len do
      m_pos = m_pos + 1
      dst = dst .. string.char(dst:byte(m_pos))
    end
  
  end

  if ilen == #src then
    return UCL_E.OK, dst
  elseif ilen < #src then
    return UCL_E.INPUT_NOT_CONSUMED, dst
  else
    return UCL_E.INPUT_OVERRUN, dst
  end

end

Реализация алгоритма шифрования RC5 на Lua. При желании использовать FSPA подписывайте сами.
Помимо базового шифрования/дешифрования блока реализовано кодирование строки в режимах ECB и CBC, но зависимость производительности от размера данных не менее крута, чем у раннего варианта NRV2E.

-- Creates RC5 codec
-- key: encryption key
-- w: word length in bits, optional
-- r: number of rounds, optional
function rc5(key, w, r)
  w, r = w or 32, r or 12

  local p = {[8] = 0xB8, [16] = 0xB7E1, [32] = 0xB7E15163}
  local q = {[8] = 0x9E, [16] = 0x9E37, [32] = 0x9E3779B9}
  local m = 2 ^ w
  local ws = w / 8

  local function rotl(a, b)
    b = b % w
    local c = 2 ^ (w - b)
    b = 2 ^ b
    return a % c * b + math.floor(a / c)
  end

  local function rotr(a, b)
    b = b % w
    local c = 2 ^ (w - b)
    b = 2 ^ b
    return a % b * c + math.floor(a / b)
  end

  local function xor(a, b)
    local c, pow = 0, 1
    local xorl = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 0}}
    while a > 0 or b > 0 do
      c = c + xorl[a % 2][b % 2] * pow
      a = math.floor(a / 2)
      b = math.floor(b / 2)
      pow = pow * 2
    end
    return c
  end
  
  local codec = {
    s = {},

    -- Encodes block w1:w2
    encode = function(self, w1, w2)
      w1 = (w1 + self.s[0]) % m
      w2 = (w2 + self.s[1]) % m
      for i = 1, r do
        w1 = (rotl(xor(w1, w2), w2) + self.s[2 * i]) % m
        w2 = (rotl(xor(w2, w1), w1) + self.s[2 * i + 1]) % m
      end
      return w1, w2
    end,

    -- Decodes block w1:w2
    decode = function(self, w1, w2)
      for i = r, 1, -1 do
        w2 = xor(rotr((w2 - self.s[2 * i + 1]) % m, w1), w1)
        w1 = xor(rotr((w1 - self.s[2 * i]) % m, w2), w2)
      end
      w2 = (w2 - self.s[1]) % m
      w1 = (w1 - self.s[0]) % m
      return w1, w2
    end,
    
    -- Splits string str to block
    split = function(self, str)
      local w1, w2, mul = 0, 0, 1
        for i = 1, ws do
          w1 = w1 + (str:byte(i) or 0) * mul
          w2 = w2 + (str:byte(i + 4) or 0) * mul
          mul = 256 * mul
        end
      return w1, w2
    end,
    
    -- Joins block w1:w2 to string
    join = function(self, w1, w2)
      local res = ""
      for i = 1, ws do
        res = res .. string.char(w1 % 256)
        w1 = math.floor(w1 / 256)
      end
      for i = 1, ws do
        res = res .. string.char(w2 % 256)
        w2 = math.floor(w2 / 256)
      end
      return res
    end,

    -- Encodes/decodes string str in ECB mode
    -- f: codec.encode or codec.decode
    ecb = function(self, f, str)
      local res = ""
      while #res < #str do
        res = res .. self:join(f(self, self:split(str:sub(#res + 1, #res + 2 * ws + 1))))
      end
      return res
    end,
    
    -- Encodes string str in CBC mode
    -- iv1, iv2: initialization vector, optional
    cbc_encode = function(self, str, iv1, iv2)
      iv1, iv2 = iv1 or 0, iv2 or 0
      local res = ""
      while #res < #str do
        local w1, w2 = self:split(str:sub(#res + 1, #res + 2 * ws + 1))
        iv1, iv2 = self:encode(xor(iv1, w1), xor(iv2, w2))
        res = res .. self:join(iv1, iv2)
      end
      return res
    end,
    
    -- Decodes string str in CBC mode
    -- iv1, iv2: initialization vector, optional
    cbc_decode = function(self, str, iv1, iv2)
      iv1, iv2 = iv1 or 0, iv2 or 0
      local res = ""
      while #res < #str do
        local w1, w2 = self:split(str:sub(#res + 1, #res + 2 * ws + 1))
        local dw1, dw2 = self:decode(w1, w2)
        res = res .. self:join(xor(iv1, dw1), xor(iv2, dw2))
        iv1, iv2 = w1, w2
      end
      return res
    end
  }

  local c = math.ceil(8 * math.max(#key, 1) / w)
  local t = 2 * (r + 1)
  local l = {}
  
  for i = #key - 1, 0, -1 do
    local j = math.floor(8 * i / w)
    l[j] = (l[j] or 0) * 256 + key:byte(i + 1)
  end

  codec.s[0] = p[w]
  for i = 1, t do
    codec.s[i] = (codec.s[i - 1] + q[w]) % m
  end

  local a, b, i, j = 0, 0, 0, 0
  for k = 1, 3 * math.max(t, c) do
    codec.s[i] = rotl((codec.s[i] + a + b) % m, 3)
    a = codec.s[i]
    l[j] = rotl((l[j] + a + b) % m, (a + b) % m)
    b = l[j]
    i = (i + 1) % t
    j = (j + 1) % c
  end

  return codec
end

Выводы:
1) Использование строк как бинарного буфера в луа — очень, очень медленно (вернее, читается-то оно нормально, но писать в такой буфер можно только конкатенацией — и это очень медленно, как только строка становится достаточно длинной).
2) С bitwise-операциями в Lua 5.1 лучше не связываться. На Lua 5.2+ RC5 можно резко ускорить, переведя его с эстонского битвайза на bit32.
3) Оберхеймер крут, но изучать его код…

P.S. Квиксорт в ФП-стиле на луа. Как оно работает и как этим пользоваться — не помню :)

-- (defn qsort [[x & xs]]
--    (letfn [(f [g] (qsort (filter #(g % x) xs)))]
--      (when x (lazy-cat (f <) [x] (f >=)))))

function concat(t1, t2, ...)
  if (...) then
    concat(t2, ...)
  end
  for _, v in ipairs(t2) do
    table.insert(t1, v)
  end
  return t1
end

function filter(f, v, ...)
  if v then
    if f(v) then
      return v, filter(f, ...)
    else
      return filter(f, ...)
    end
  end
end

function qsort(x, ...)

  local function f(g, ...)
    return qsort(filter(g, ...))
  end
  
  if x then
    return unpack(concat({f(function(v) return v<x end, ...)}, {x}, {f(function(v) return v>=x end, ...)}))
  end

end

Update 02.07.2016

Алгоритм хэширования SHA1 и расширенный эстонский битвайз:

local function byte(num, n)
  if n > 0 then
    num = math.floor(num / 256 ^ n)
  end
  return num % 256
end

local function rotl32(a, b)
  b = b % 32
  local c = 2 ^ (32 - b)
  b = 2 ^ b
  return a % c * b + math.floor(a / c)
end

local function rotr32(a, b)
  b = b % 32
  local c = 2 ^ (32 - b)
  b = 2 ^ b
  return a % b * c + math.floor(a / b)
end

local function bw(op, a, b)
  local c, pow = 0, 1
  while a > 0 or b > 0 do
    c = c + op[a % 2][b % 2] * pow
    a = math.floor(a / 2)
    b = math.floor(b / 2)
    pow = pow * 2
  end
  return c
end

local function bw3(op, a, b, c)
  local r, pow = 0, 1
  while a > 0 or b > 0 or c > 0 do
    r = r + op[a % 2][b % 2][c % 2] * pow
    a = math.floor(a / 2)
    b = math.floor(b / 2)
    c = math.floor(c / 2)
    pow = pow * 2
  end
  return r
end

local bnot32 = 0xFFFFFFFF
local opor = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 1}}
local opand = {[0] = {[0] = 0, [1] = 0}, [1] = {[0] = 0, [1] = 1}}
local opxor = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 0}}

local opsel = {[0] = {[0] = {[0] = 0, [1] = 0}, [1] = {[0] = 0, [1] = 1}}, [1] = {[0] = {[0] = 1, [1] = 0}, [1] = {[0] = 1, [1] = 1}}}
local opmaj = {[0] = {[0] = {[0] = 0, [1] = 0}, [1] = {[0] = 0, [1] = 1}}, [1] = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 1}}}
local opxor3 = {[0] = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 0}}, [1] = {[0] = {[0] = 1, [1] = 0}, [1] = {[0] = 0, [1] = 1}}}

function sha1(msg)
  local mlen = #msg * 8
  if mlen > 0xFFFFFFFF then
    error('Msg is too big')
  end
  msg = msg .. string.char(0x80)
  while #msg % 64 ~= 56 do
    msg = msg .. string.char(0x00)
  end
  msg = msg .. string.char(0x00, 0x00, 0x00, 0x00)
  for i = 3, 0, -1 do
    msg = msg .. string.char(byte(mlen, i))
  end
  local h = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0}
  for block = 0, #msg / 64 - 1 do
    local w = {}
    for i = 0, 15 do
      w[i] = 0
      for b = 1, 4 do
        w[i] = 256 * w[i] + msg:byte(64 * block + 4 * i + b)
      end
    end
    for i = 16, 79 do
      w[i] = rotl32(bw(opxor, bw(opxor, w[i - 3], w[i - 8]), bw(opxor, w[i - 14], w[i - 16])), 1)
    end
    local a, b, c, d, e = h[1], h[2], h[3], h[4], h[5]
    for i = 0, 79 do
      local k, f
      if i < 20 then
        f = bw3(opsel, d, c, b)
        k = 0x5A827999
      elseif i < 40 then
        f = bw3(opxor3, b, c, d)
        k = 0x6ED9EBA1
      elseif i < 60 then
        f = bw3(opmaj, b, c, d)
        k = 0x8F1BBCDC
      else
        f = bw3(opxor3, b, c, d)
        k = 0xCA62C1D6
      end
      a, b, c, d, e = (rotl32(a, 5) + f + e + k + w[i]) % 2 ^ 32, a, rotl32(b, 30), c, d
    end
    h[1], h[2], h[3], h[4], h[5] = (h[1] + a) % 2 ^ 32, (h[2] + b) % 2 ^ 32, (h[3] + c) % 2 ^ 32, (h[4] + d) % 2 ^ 32, (h[5] + e) % 2 ^ 32
  end
  local res = ""
  for i = 1, 5 do
    for j = 3, 0, -1 do
      res = res .. string.char(byte(h[i], j))
    end
  end
  return res  
end