Fun with metatables: Infix bitwise operators

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Fun with metatables: Infix bitwise operators

Rena
Recently I was porting to Lua some horribly messy decompiled code like:
x = (((((Param[1] & 0xF) << 0x12) | (((Param[1] & 0xF0) >> 4) << 0xE))
| ((Param[0] & 0xF) << 8)) | (((Param[0] & 0xF0) >> 4) << 4))

I thought, trying to convert such a mess to prefix (bit.band(a,b)
rather than a & b) would be a nightmare, and it sure would be nice if
I had infix bitwise operators instead. So I threw together this little
module:

local ops = {}
local bit = require('bit')

ops['<<'] = bit.lshift
ops['>>'] = bit.rshift
ops['|'] = bit.bor
ops['&'] = bit.band
ops['^'] = bit.bxor
ops['lsh'] = bit.lshift
ops['rsh'] = bit.rshift
ops['or'] = bit.bor
ops['and'] = bit.band
ops['xor'] = bit.bxor
ops['arsh'] = bit.arshift
ops['rol'] = bit.rol
ops['ror'] = bit.ror

debug.setmetatable(0, {
        __call = function(p1, op)
                return setmetatable({}, {
                        __call = function(_, p2)
                                return ops[op](p1, p2)
                        end,
                })
        end,
})

It's quite a hack, and still a bit ugly because it's actually abusing
function call syntax, so rather than "1 << n", you have to write "(1)
'<<' (n)", but it works. I thought some others might find this
interesting. :-)

I'd call this public domain code, but given the debates recently about
whether that has any meaning, I suppose I should release it under the
MIT license instead. :-)

As an example, that messy fragment above (after stripping some
redundant shifts) looks like:
x = (((h) '&' (0x0F)) '<<' (0x12))
  '|' (((h) '&' (0xF0)) '<<' (0xA))
  '|' (((w) '&' (0x0F)) '<<' (8))
  '|' ((w) '&' (0xF0))
Still a bit ugly, but at least you can get an idea what it's doing now! ;-)

--
Sent from my toaster.

Reply | Threaded
Open this post in threaded view
|

Re: Fun with metatables: Infix bitwise operators

David Manura
On Fri, Sep 9, 2011 at 11:47 PM, HyperHacker <[hidden email]> wrote:
> so rather than "1 << n", you have to write "(1) '<<' (n)"  [...]
> x = (((h) '&' (0x0F)) '<<' (0x12))
>  '|' (((h) '&' (0xF0)) '<<' (0xA))
>  '|' (((w) '&' (0x0F)) '<<' (8))
>  '|' ((w) '&' (0xF0))

I don't seriously consider doing that type of thing [1] in real code,
though I wonder if LuaJit can work its magic on these approaches.  I
would rather do the ordinary:

  local O, A, L = bit.bor, bit.band, bit.lshift
  x = O( L(A(h, 0x0F), 0x12),
            L(A(h, 0xF0), 0xA),
            L(A(w, 0x0F), 8),
               A(w, 0xF0)         )

You can also do this:

  debug.setmetatable(0, {__index = require'bit32'})
  x = (0):bor(
    h:band(0x0F):lshift(0x12),
    h:band(0xF0):lshift(0xA),
    w:band(0x0F):lshift(8),
    w:band(0xF0)
  )

Under one of the syntax proposals, we could refine that to

  x = (0):['|'](
    h:['&'](0x0F):['<<'](0x12),
    h:['&'](0xF0):['<<'](0xA),
    w:['&'](0x0F):['<<'](8),
    w:['&'](0xF0)
  )

However, rather than abuse Lua syntax, it's more general to pass a
list of "tokens" to an evaluator:

  x = eval(
    '(', h, '&', 0x0F, '<<', 0x12, ')', '|',
    '(', h, '&', 0xF0, '<<', 0xA, ')', '|',
    '(', w, '&', 0x0F, '<<', 8, ')', '|',
    '(', w, '&', 0xF0, ')'
  )

A code generation technique like in [2] could make that quite efficient:

  x = eval[[
    ((P1 & 0x0F) << 0x12) |
    ((P1 & 0xF0) << 0xA) |
    ((P2 & 0x0F) << 8) |
    ((P2 & 0xF0 )
  ]](h, w)

[1] http://lua-users.org/wiki/CustomOperators
[2] http://lua-users.org/wiki/ListComprehensions

Reply | Threaded
Open this post in threaded view
|

Re: Fun with metatables: Infix bitwise operators

David Manura
On Sat, Sep 10, 2011 at 1:07 AM, David Manura <[hidden email]> wrote:
> A code generation technique like in [2] could make that quite efficient:

And this is another case where it would be nice if Lua syntax allowed
string interpolation [3]:

  x = eval "
    ((${h} & 0x0F) << 0x12) |
    ((${h} & 0xF0) << 0xA) |
    ((${w} & 0x0F) << 8) |
     (${w} & 0xF0 )
  "

My preference for how Lua would handle string interpolation [4] would
be for the lexer to translate `eval" ${x} & ${y} "` into something
like `eval(" ${x} & ${y} ", x, y)`.  You could then implement eval to
compile " ${x} & ${y} " into a function and cache it using the string
as a key, so subsequent calls would be fast.  One alternative at the
moment is IMO not very readable because the brackets don't appear to
nest, and it is not as efficient to do the cache lookup when the
string is broken into smaller ones:

 x = eval([[
    ((]], h, [[ & 0x0F) << 0x12) |
    ((]], h, [[ & 0xF0) << 0xA) |
    ((]], w, [[ & 0x0F) << 8) |
     (]], w, [[ & 0xF0 )
  ]])

[3] http://lua-users.org/wiki/StringInterpolation
[4] http://lua-users.org/lists/lua-l/2009-05/msg00248.html

Reply | Threaded
Open this post in threaded view
|

Re: Fun with metatables: Infix bitwise operators

Dirk Laurie
In reply to this post by Rena
On Sat, Sep 10, 2011 at 05:47:07AM +0200, HyperHacker wrote:
> Recently I was porting to Lua some horribly messy decompiled code like:
> x = (((((Param[1] & 0xF) << 0x12) | (((Param[1] & 0xF0) >> 4) << 0xE))
> | ((Param[0] & 0xF) << 8)) | (((Param[0] & 0xF0) >> 4) << 4))
>
> I thought, trying to convert such a mess to prefix (bit.band(a,b)
> rather than a & b) would be a nightmare, and it sure would be nice if
> I had infix bitwise operators instead.
...
> debug.setmetatable(0, {
...
> As an example, that messy fragment above (after stripping some
> redundant shifts) looks like:
> x = (((h) '&' (0x0F)) '<<' (0x12))
>   '|' (((h) '&' (0xF0)) '<<' (0xA))
>   '|' (((w) '&' (0x0F)) '<<' (8))
>   '|' ((w) '&' (0xF0))

If you're not married to C operator notation, another way is to override
existing metamethods for +, *, indexing etc.  Then your messy fragment
becomes (with the aid of the file below):

    bits = require "bit32ops"
    Param = {0x86,0xE7}
    w, h = bits(Param[0]), bits(Param[1])  
    n0, n1 = 0xF, 0xF0
    x = (h*n0)^-18 + (h*n1)^-10 + (w*n0)^-8 + w*n1
    print(x)   --> 0x1F8680

Dirk

~~~~ file bit32ops.lua
--[[
bits.lua  (c) Dirk Laurie 2011
Released under the LHF public-domain license:
<http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/install.html#license>

Infix operations on 32-bit values

Method: the 32-bit value is the entry 'value' of a table.

The following metamethods are available for use in expressions, with
precedences of the corresponding operators from top (highest) to bottom:

index call
pow
len unm
mul div mod
add sub
concat
eq ne lt le gt ge

The following bit32 operations are available, which can be mapped as
follows:

bnot                <==>    unm
band                <==>    mul
btest               <==>    mod
bor                 <==>    add
bxor                <==>    sub
rshift              <==>    pow
extract, replace    <==>    call
rrotate            <==>    index
arshift            <==>    concat

That leaves len, to convert back from `bits` to `number`.

lshift and lrotate can of course be done by rshift and rrotate.
The choice that right is positive, rather than left, is dictated
by the fact that arithmetic shift leaves no choice. A further emphasis
of the uniqueness of arshift is that its precedence is anomalous.

If the second argument of a function is a 32-bit value, it may
given as either be a table having a key 'value' or a number.  

Restrictions:
1. many-argument use of band, btest, bor, bxor is not supported
2. 'replace' must have three arguments, value, field, width,
   no default allowed.
   However, 'extract' may have only one argument, field: width=1 is supplied.

--]]

local val = function(b32)
    if type(b32)=='table' then return b32.value
    else return b32
    end end

local bits

bits = {
-- return number
__len = function (b32) return b32.value end;
-- return bits
__unm = function (b32) return bits(bit32.bnot(b32.value)) end;
__mul = function (a32,b32) return bits(bit32.band(a32.value,val(b32))) end;
__add = function (a32,b32) return bits(bit32.bor(a32.value,val(b32))) end;
__sub = function (a32,b32) return bits(bit32.bxor(a32.value,val(b32))) end;
__pow = function (a32,b) return bits(bit32.rshift(a32.value,b)) end;
__index = function (a32,b) return bits(bit32.rrotate(a32.value,b)) end;
__concat = function (a32,b) return bits(bit32.arshift(a32.value,b)) end;
__call = function (b32,x,y,z)
    if z==nil then return bits(bit32.extract(b32.value,x,y))
    else return bits(bit32.replace(b32.value,val(x),y,z))
        end end;
-- return string
__tostring = function(b32) return string.format('0x%X',b32.value) end;
-- return boolean
__mod = function (a32,b32) return bit32.btest(a32.value,val(b32)) end;
__eq = function (a32,b32) return a32.value==val(b32) end;
__ne = function (a32,b32) return a32.value~=val(b32) end;
__le = function (a32,b32) return a32.value<=val(b32) end;
__lt = function (a32,b32) return a32.value<val(b32) end;
__ge = function (a32,b32) return a32.value>=val(b32) end;
__gt = function (a32,b32) return a32.value>val(b32) end;
}

setmetatable(bits,{
__call = function(self,v)
    local b32 = {value=v}
    setmetatable (b32,self)
    return b32
    end
} )

return bits

--[[ EXAMPLES
B=require"bit32ops"
x=B(639); print(x,#x,-x,#-x)      -->   0x27F  639  0xFFFFFD80  4294966656
y=B(159); print(y,x*y,x%y,x*159)  -->   0x9F  0x1F  true  0x1F
print(x+y,x-y)                    -->   0x2FF  0x2E0
print(x^-3,x^1,x[1],-x..1)        -->   0x13F8  0x13F  0x8000013F  0xFFFFFEC0
print(x(0,8))                     -->   0x7F
print(x(0xf,24,4))                -->   0xF00027F
print(-x,(-x)..6,(-x)..6>-x)      -->   0xFFFFFD80  0xFFFFFFF6  true
--]]
~~~~ end of file