CRC32 implimentation returns a map of all 0s

Questions / Help
,
1

Hello again.

Im currently writing a png decoder/encoder and I’ve run into an issue with my CRC32 function (shown below)

def crc32_table() do
    power_hex = 0xEDB88320
    Enum.into(0..256, %{}, fn(x)->
      current = x
      crc = 0
      for _ <- 0..8 do
        b = Integer.pow(current, crc) &&& 1
        crc = crc >>> 1
        if(b) do crc = Integer.pow(crc, power_hex) end
        current = current >>> 1
      end
      {x, crc}
    end)
  end

I used the Bytewise implimentation from here as reference, but my elixir knowledge is a little rough (im new).

When outputing to a file, it shows my whole map is equal to 0, which causes our favourite, high fan speeds and a hanging process when run through my decoder.

Is there anything immediately wrong to more experienced elixir devs? I could just be overlooking something and flooding the forum…

Thank you for, one, the tolerance here, and two, all the help. This is an S tier forum!

2

As a little extra note, I assume nothings being written into the crc value in the for loop, and its just returning… Im not sure on why though

3

In your for loop, you attempt to modify crc and current like you would do in C. This won’t work in Elixir though, as the new binding only affects the value of crc and current inside the block and does not change the binding outside:

c = 0

for _ <- 0..10 do
  c = c + 1
end

# The for loop returns [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (not [1, 2, 3, 4, 5, ...])
# also, here c is still 0
1 Like
4

Im not sure how I overlooked such a fundemental concept, i mean it is Immutabilty after all… Would the correct method be to make this an actual recurssive function which halts returning the crc?

Along the lines of

  def crc32_table() do
    Enum.into(0..256, %{}, fn(x)->
      current = x
      crc = crc32_table_loop(0, current, 7)
      {x, crc}
    end)
  end

  defp crc32_table_loop(crc, curr, iters) when iters < 1 do
    power_hex = 0xEDB88320
    b = Integer.pow(curr, crc) &&& 1
    crc = crc >>> 1
    if(b) do crc = Integer.pow(crc, power_hex) end
    crc
  end

  defp crc32_table_loop(crc, curr, iters) do
    power_hex = 0xEDB88320
    b = Integer.pow(curr, crc) &&& 1
    crc = crc >>> 1
    if(b) do crc = Integer.pow(crc, power_hex) end
    curr = curr >>> 1
    crc32_table_loop(crc, curr, iters - 1)
  end

Scrappy I know, but i have a feeling that im just not used to working without side effects yet.

5

Also, as I understand, in the original code you linked x ^ y is a XOR operation, not an exponentiation, so instead of Integer.pow you should use bxor.

1 Like
6

…

You are right… Im am clearly a novice at this :laughing:

Should of read the assembly

7

Please note that I did not test the snippet that follows, so make sure you test it, but here is a modified version of your code that should behave like you intended. It can be written in more idiomatic ways, but I tried to keep it as close as possible to your original code, to be more understandable:


  def crc32_table() do
    power_hex = 0xEDB88320
    Enum.into(0..256, %{}, fn(x)->
      {_, crc} = Enum.reduce(0..8, {x, 0}, fn(_, {current, crc}) ->
        b = bxor(current, crc) &&& 1
        crc = if (b != 0) do
          bxor(crc >>> 1, power_hex)
        else
          crc >>> 1
        end
        {current >>> 1, crc}
      end)

      {x, crc}
    end)
  end
2 Likes
8

Thank you for all the help, ill give this a test and tweak and mark it as a solution once I have

I really appricate the patience, this is such a breath of fresh air from stack overflow!

Yep its perfect, got what i was expecting, popped your credit in too. Hopefully my brain retains this knowledge, and I rtfm first next time (and pay more attention) haha!

2 Likes
9

Equivalently, but using for comprehension:

def crc32_table() do
  power_hex = 0xEDB88320

  for x <- 0..256, into: %{} do 
    {_, crc} = for _ <- 0..8, reduce: {x, 0} do
      {current, crc} when band(bxor(current, crc), 1) == 0 ->
        {current >>> 1, crc >>> 1}

      {current, crc} ->
        {current >>> 1, bxor(crc >>> 1, power_hex)}
    end

    {x, crc}
  end
end
2 Likes
10

And the whole code if anyone want to make use of it, now tested against know values, and working.

Marked as solution, but all credit goes to Lucaong

defmodule CheckSum do
  # Thanks to Lucaong for saving me in the post: https://elixirforum.com/t/crc32-implimentation-returns-a-map-of-all-0s/57956/8
  def crc32_table() do
    power_hex = 0xEDB88320
    Enum.into(0..255, %{}, fn(x)->
      {_, crc} = Enum.reduce(0..7, {x, 0}, fn (_, {current, crc}) ->
        b = bxor(current, crc) &&& 1
        crc = if (b != 0) do
          bxor(crc >>> 1, power_hex)
        else
          crc >>> 1
        end
        {current >>> 1, crc}
      end)
      {x, crc}
    end)
  end

  # slower to call without a lookup table, pre-generating one is way faster
  def crc32_fast(data, size) do
    table = crc32_table()
    crc32_fast(data, size, table)
  end

  def crc32_fast(data, size, table) do
    crc = Enum.reduce(0..size-1, 0xFFFFFFFF , fn(i, crc) ->
      c = :binary.at(data, i)
      table_index = bxor(c, crc) &&& 0xFF
      bxor((crc >>> 8), table[table_index])
    end)
    to_u32(bxor(crc, 0xFFFFFFFF))
  end

  def to_u32(num) when num >= 0 do
    num
  end
  def to_u32(<<num::little-signed-integer-size(32)>>) do
    num
  end
end

My ranges were 1 off