CRC16 ccitt 1021 - Part 1

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

CRC16 ccitt 1021 - Part 1

Russell Haley
Hi,

Can anybody help me convert this 5.2 code to 5.3? I suck at binary stuff.

Original:

-- Author: Clark Li <[hidden email]>
-- Ported from http://introcs.cs.princeton.edu/java/51data/CRC16CCITT.java.html-- Author: Clark Li <[hidden email]>
-- Ported from http://introcs.cs.princeton.edu/java/51data/CRC16CCITT.java.html
local POLY = 0x1021
function ccitt_16(byte_array)

  local function hash(crc, byte)
    for i = 0, 7 do
      local bit = bit32.extract(byte, 7 - i) -- Take the lsb
      local msb = bit32.extract(crc, 15, 1) -- msb
      crc = bit32.lshift(crc, 1) -- Remove the lsb of crc
      if bit32.bxor(bit, msb) == 1 then crc = bit32.bxor(crc, POLY) end
    end
    return crc
  end

  local crc = 0xffff
  for i in ipairs(byte_array) do
    crc = hash(crc, byte_array[i])
  end

  return bit32.extract(crc, 0, 16)
end


My attempts to replicate bit32.extract yielded little worth posting:

local POLY = 0x1021
function ccitt_16_l(byte_array)

    local function hash(crc, byte)
        for i = 0, 7 do
            local bit = bit32.extract(byte, 7 - i) -- Take the lsb
            local msb = bit32.extract(crc, 15, 1) -- msb
            if (bit ~ msb) == 1 then
            crc = crc ~ POLY end
        end
        return crc
    end

    local crc = 0xffff
    for i in ipairs(byte_array) do
    crc = hash(crc, byte_array[i])
    end

    return crc & 0xffff
end

Part 2 to come...

Russ
Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 1

Jonathan Goble
On Wed, Oct 23, 2019 at 11:44 PM Russell Haley <[hidden email]> wrote:
>
> Hi,
>
> Can anybody help me convert this 5.2 code to 5.3? I suck at binary stuff.
>
> My attempts to replicate bit32.extract yielded little worth posting:

It may help to look at the source code for bit32.extract:
https://www.lua.org/source/5.2/lbitlib.c.html#b_extract

The function is quite short, and the actual work with bitwise
operations is a one-liner (if you consider the "mask" macro to be part
of that one-liner). It essentially right-shifts it by an amount equal
to the desired low bit, then ANDs it with a mask equal in width to the
desired field size (which in your case is just 1).

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 1

Francisco Olarte
In reply to this post by Russell Haley
Russell:

On Thu, Oct 24, 2019 at 5:44 AM Russell Haley <[hidden email]> wrote:
> function ccitt_16(byte_array)

Your bit32 functions have already been answered, I'd just like to
point yuou that, if you need CRC, nobody calculates it bit-by-bit.
There are ways to do it N bits at a time with the aid of a 2^n entries
lookup table ( wikipedia and other sources explain the math behind
this and there are plenty of implementations floating around ),
typically with N=8, a byte at a time, as this avoids all the
complexity of bit-extracting ( I've done ccitt 16  it this way, and
besides being much simpler and faster part of the space for the 256
entries tables is offset by the lack of bit-twiddling code, so it ends
up not that much bigger, but this was in C where the table is 512
bytes, not lua where the straight table approach ( you can use a 512
bytes string instead ) is much biger ).

Francisco Olarte.

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 1

Sergey Kovalev
In reply to this post by Jonathan Goble
local bit32={}
bit32.extract=function(x,s,n) n=n or 1 return (x>>s)&((1<<n)-1) end
bit32.lshift=function(x,n) return x<<n end
bit32.bxor=function(a,b) return a~b end

чт, 24 окт. 2019 г. в 07:31, Jonathan Goble <[hidden email]>:

>
> On Wed, Oct 23, 2019 at 11:44 PM Russell Haley <[hidden email]> wrote:
> >
> > Hi,
> >
> > Can anybody help me convert this 5.2 code to 5.3? I suck at binary stuff.
> >
> > My attempts to replicate bit32.extract yielded little worth posting:
>
> It may help to look at the source code for bit32.extract:
> https://www.lua.org/source/5.2/lbitlib.c.html#b_extract
>
> The function is quite short, and the actual work with bitwise
> operations is a one-liner (if you consider the "mask" macro to be part
> of that one-liner). It essentially right-shifts it by an amount equal
> to the desired low bit, then ANDs it with a mask equal in width to the
> desired field size (which in your case is just 1).
>

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 1

Russell Haley


On Fri, Oct 25, 2019 at 3:47 PM Sergey Kovalev <[hidden email]> wrote:
local bit32={}
bit32.extract=function(x,s,n) n=n or 1 return (x>>s)&((1<<n)-1) end
bit32.lshift=function(x,n) return x<<n end
bit32.bxor=function(a,b) return a~b end
Much thanks. That was bugging me but I don't want to get distracted.
Russ

чт, 24 окт. 2019 г. в 07:31, Jonathan Goble <[hidden email]>:
>
> On Wed, Oct 23, 2019 at 11:44 PM Russell Haley <[hidden email]> wrote:
> >
> > Hi,
> >
> > Can anybody help me convert this 5.2 code to 5.3? I suck at binary stuff.
> >
> > My attempts to replicate bit32.extract yielded little worth posting:
>
> It may help to look at the source code for bit32.extract:
> https://www.lua.org/source/5.2/lbitlib.c.html#b_extract
>
> The function is quite short, and the actual work with bitwise
> operations is a one-liner (if you consider the "mask" macro to be part
> of that one-liner). It essentially right-shifts it by an amount equal
> to the desired low bit, then ANDs it with a mask equal in width to the
> desired field size (which in your case is just 1).
>

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 1

Philipp Janda
In reply to this post by Sergey Kovalev
Am 25.10.19 um 23:02 schröbte Sergey Kovalev:
> local bit32={}
> bit32.extract=function(x,s,n) n=n or 1 return (x>>s)&((1<<n)-1) end
> bit32.lshift=function(x,n) return x<<n end
> bit32.bxor=function(a,b) return a~b end

The Lua test suite for Lua 5.3 contains a bit32 implementation in pure
Lua using the bit operators.

Philipp