Луевости

Декомпрессор 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
- +2
- 02 июня 2016, 19:54
- Vga
- 1
Файлы в топике:
RC5.lua.txt
По прилагающемуся мануальчику. И, возможно, немного по сторонним материалам, которые уже не помню. Кроме мануальчика могу порекомендовать книгу Programming in Lua, которую, впрочем, не читал.
А может напишешь статейку, в которой повествуеться: где взять компилятор? Как с ним работать? Как кодить на Lua? И что с этим можно будет сделать и зачем это все надо?
Я знаю например, что Lua используется для прямого программирования модуля Wi-Fi ESP8266.
Я знаю например, что Lua используется для прямого программирования модуля Wi-Fi ESP8266.
Lua достаточно легко подключается к своим программам на С, С#, С++ как скриптовый язык (ессно, с двухсторонними связями луа-свой код). Вполне возможно, что и в контроллер запихать можно, как это сделано в упомянутом esp8266, и брать программки с какой-нибудь сд-карты или из сети.
Может быть, он не очень привычный, но своё очарование всё же имеет.
Может быть, он не очень привычный, но своё очарование всё же имеет.
- teplofizik
- 03 июня 2016, 17:30
- ↑
- ↓
Хорошо, а можно ли каким нибудь образом запихнуть интерпретатор Lua в микроконтроллер, например STM32, а потом подкидывать этому STM32 программки написанные на Lua и пусть их выполняет?
Я читал мануал на английском (и вообще в программировании без английского делать нечего). Но есть и русские переводы.
Да, она как раз заточена под embedded приложения, вот поддерживаемые платформы:
github.com/elua/elua/tree/master/src/platform
github.com/elua/elua/tree/master/src/platform
где взять компилятор?Луа, вообще-то, интерпретатор. Живет на www.lua.org. Кроме оригинальной версии, некоторый интерес представляют LuaJIT и Lua for Windows (это большая сборка библиотек к луа).
Как с ним работать?В мане все написано, там все просто.
Как кодить на Lua?Ровно об этом пишет книга Programming in Lua (PiL).
И что с этим можно будет сделать и зачем это все надо?Основное назначение Lua — встраивание в свое ПО как скриптового движка. В том числе — embedded, ESP8266 как раз пример этого случая. Также можно использовать standalone-интерпретатор для написания программок/утилиток на компе, как раз для этого варианта Lua for Windows и предназначен.
А может напишешь статейкуПоскольку кроме вышеприведенного мне особо сказать нечего — нет.
Комментарии (21)
RSS свернуть / развернуть