Created
November 25, 2018 17:47
-
-
Save tomciopp/2d174f3960b6386e86167268b1a9875d to your computer and use it in GitHub Desktop.
Pure Elixir/Erlang CRC32C implementations
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
I have tested the elixir version and it works, but have not tested the erlang version of this code. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-module(cyclic_redundancy_check). | |
-export([crc32c/1]) | |
-define(CRC32C_TABLE, { | |
16#00000000, 16#F26B8303, 16#E13B70F7, 16#1350F3F4, | |
16#C79A971F, 16#35F1141C, 16#26A1E7E8, 16#D4CA64EB, | |
16#8AD958CF, 16#78B2DBCC, 16#6BE22838, 16#9989AB3B, | |
16#4D43CFD0, 16#BF284CD3, 16#AC78BF27, 16#5E133C24, | |
16#105EC76F, 16#E235446C, 16#F165B798, 16#030E349B, | |
16#D7C45070, 16#25AFD373, 16#36FF2087, 16#C494A384, | |
16#9A879FA0, 16#68EC1CA3, 16#7BBCEF57, 16#89D76C54, | |
16#5D1D08BF, 16#AF768BBC, 16#BC267848, 16#4E4DFB4B, | |
16#20BD8EDE, 16#D2D60DDD, 16#C186FE29, 16#33ED7D2A, | |
16#E72719C1, 16#154C9AC2, 16#061C6936, 16#F477EA35, | |
16#AA64D611, 16#580F5512, 16#4B5FA6E6, 16#B93425E5, | |
16#6DFE410E, 16#9F95C20D, 16#8CC531F9, 16#7EAEB2FA, | |
16#30E349B1, 16#C288CAB2, 16#D1D83946, 16#23B3BA45, | |
16#F779DEAE, 16#05125DAD, 16#1642AE59, 16#E4292D5A, | |
16#BA3A117E, 16#4851927D, 16#5B016189, 16#A96AE28A, | |
16#7DA08661, 16#8FCB0562, 16#9C9BF696, 16#6EF07595, | |
16#417B1DBC, 16#B3109EBF, 16#A0406D4B, 16#522BEE48, | |
16#86E18AA3, 16#748A09A0, 16#67DAFA54, 16#95B17957, | |
16#CBA24573, 16#39C9C670, 16#2A993584, 16#D8F2B687, | |
16#0C38D26C, 16#FE53516F, 16#ED03A29B, 16#1F682198, | |
16#5125DAD3, 16#A34E59D0, 16#B01EAA24, 16#42752927, | |
16#96BF4DCC, 16#64D4CECF, 16#77843D3B, 16#85EFBE38, | |
16#DBFC821C, 16#2997011F, 16#3AC7F2EB, 16#C8AC71E8, | |
16#1C661503, 16#EE0D9600, 16#FD5D65F4, 16#0F36E6F7, | |
16#61C69362, 16#93AD1061, 16#80FDE395, 16#72966096, | |
16#A65C047D, 16#5437877E, 16#4767748A, 16#B50CF789, | |
16#EB1FCBAD, 16#197448AE, 16#0A24BB5A, 16#F84F3859, | |
16#2C855CB2, 16#DEEEDFB1, 16#CDBE2C45, 16#3FD5AF46, | |
16#7198540D, 16#83F3D70E, 16#90A324FA, 16#62C8A7F9, | |
16#B602C312, 16#44694011, 16#5739B3E5, 16#A55230E6, | |
16#FB410CC2, 16#092A8FC1, 16#1A7A7C35, 16#E811FF36, | |
16#3CDB9BDD, 16#CEB018DE, 16#DDE0EB2A, 16#2F8B6829, | |
16#82F63B78, 16#709DB87B, 16#63CD4B8F, 16#91A6C88C, | |
16#456CAC67, 16#B7072F64, 16#A457DC90, 16#563C5F93, | |
16#082F63B7, 16#FA44E0B4, 16#E9141340, 16#1B7F9043, | |
16#CFB5F4A8, 16#3DDE77AB, 16#2E8E845F, 16#DCE5075C, | |
16#92A8FC17, 16#60C37F14, 16#73938CE0, 16#81F80FE3, | |
16#55326B08, 16#A759E80B, 16#B4091BFF, 16#466298FC, | |
16#1871A4D8, 16#EA1A27DB, 16#F94AD42F, 16#0B21572C, | |
16#DFEB33C7, 16#2D80B0C4, 16#3ED04330, 16#CCBBC033, | |
16#A24BB5A6, 16#502036A5, 16#4370C551, 16#B11B4652, | |
16#65D122B9, 16#97BAA1BA, 16#84EA524E, 16#7681D14D, | |
16#2892ED69, 16#DAF96E6A, 16#C9A99D9E, 16#3BC21E9D, | |
16#EF087A76, 16#1D63F975, 16#0E330A81, 16#FC588982, | |
16#B21572C9, 16#407EF1CA, 16#532E023E, 16#A145813D, | |
16#758FE5D6, 16#87E466D5, 16#94B49521, 16#66DF1622, | |
16#38CC2A06, 16#CAA7A905, 16#D9F75AF1, 16#2B9CD9F2, | |
16#FF56BD19, 16#0D3D3E1A, 16#1E6DCDEE, 16#EC064EED, | |
16#C38D26C4, 16#31E6A5C7, 16#22B65633, 16#D0DDD530, | |
16#0417B1DB, 16#F67C32D8, 16#E52CC12C, 16#1747422F, | |
16#49547E0B, 16#BB3FFD08, 16#A86F0EFC, 16#5A048DFF, | |
16#8ECEE914, 16#7CA56A17, 16#6FF599E3, 16#9D9E1AE0, | |
16#D3D3E1AB, 16#21B862A8, 16#32E8915C, 16#C083125F, | |
16#144976B4, 16#E622F5B7, 16#F5720643, 16#07198540, | |
16#590AB964, 16#AB613A67, 16#B831C993, 16#4A5A4A90, | |
16#9E902E7B, 16#6CFBAD78, 16#7FAB5E8C, 16#8DC0DD8F, | |
16#E330A81A, 16#115B2B19, 16#020BD8ED, 16#F0605BEE, | |
16#24AA3F05, 16#D6C1BC06, 16#C5914FF2, 16#37FACCF1, | |
16#69E9F0D5, 16#9B8273D6, 16#88D28022, 16#7AB90321, | |
16#AE7367CA, 16#5C18E4C9, 16#4F48173D, 16#BD23943E, | |
16#F36E6F75, 16#0105EC76, 16#12551F82, 16#E03E9C81, | |
16#34F4F86A, 16#C69F7B69, 16#D5CF889D, 16#27A40B9E, | |
16#79B737BA, 16#8BDCB4B9, 16#988C474D, 16#6AE7C44E, | |
16#BE2DA0A5, 16#4C4623A6, 16#5F16D052, 16#AD7D5351 | |
}) | |
crc32c(data) -> crc32c(data, 16#FFFFFFFF). | |
crc32c(<<>>, acc) -> bxor(acc, 16#FFFFFFFF); | |
crc32c(<<Current:1/binary, Rest/binary>>, acc) -> | |
Index = band(bxor(acc, Current), 16#FF) + 1, | |
crc32c(Rest, bxor(bsr(acc, 8), element(Index, ?CRC32C_TABLE))). | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
defmodule CyclicRedundancyCheck do | |
use Bitwise | |
@lookup_table [ | |
0x00000000, 0xF26B8303, 0xE13B70F7, 0x1350F3F4, | |
0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB, | |
0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B, | |
0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24, | |
0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B, | |
0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384, | |
0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54, | |
0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B, | |
0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A, | |
0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35, | |
0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5, | |
0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA, | |
0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45, | |
0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A, | |
0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A, | |
0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595, | |
0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48, | |
0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957, | |
0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687, | |
0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198, | |
0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927, | |
0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38, | |
0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8, | |
0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7, | |
0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096, | |
0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789, | |
0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859, | |
0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46, | |
0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9, | |
0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6, | |
0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36, | |
0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829, | |
0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C, | |
0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93, | |
0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043, | |
0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C, | |
0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3, | |
0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC, | |
0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C, | |
0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033, | |
0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652, | |
0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D, | |
0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D, | |
0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982, | |
0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D, | |
0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622, | |
0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2, | |
0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED, | |
0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530, | |
0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F, | |
0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF, | |
0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0, | |
0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F, | |
0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540, | |
0x590AB964, 0xAB613A67, 0xB831C993, 0x4A5A4A90, | |
0x9E902E7B, 0x6CFBAD78, 0x7FAB5E8C, 0x8DC0DD8F, | |
0xE330A81A, 0x115B2B19, 0x020BD8ED, 0xF0605BEE, | |
0x24AA3F05, 0xD6C1BC06, 0xC5914FF2, 0x37FACCF1, | |
0x69E9F0D5, 0x9B8273D6, 0x88D28022, 0x7AB90321, | |
0xAE7367CA, 0x5C18E4C9, 0x4F48173D, 0xBD23943E, | |
0xF36E6F75, 0x0105EC76, 0x12551F82, 0xE03E9C81, | |
0x34F4F86A, 0xC69F7B69, 0xD5CF889D, 0x27A40B9E, | |
0x79B737BA, 0x8BDCB4B9, 0x988C474D, 0x6AE7C44E, | |
0xBE2DA0A5, 0x4C4623A6, 0x5F16D052, 0xAD7D5351 | |
] | |
def crc32c(data), do: crc32c(data, 0xFFFFFFFF) | |
def crc32c(<<>>, acc), do: bxor(acc, 0xFFFFFFFF) | |
def crc32c(<<current :: size(8), data :: binary>>, acc) do | |
index = acc |> bxor(current) |> band(0xFF) | |
crc32c(data, bxor(bsr(acc, 8), Enum.at(@lookup_table, index))) | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for posting this! Just a tip, you can improve performance of the elixir implementation by replacing the
Enum.at
and lookup table with a function call using pattern matching like this:A simple benchee benchmark gave me results 15x faster using this approach.
Results: