Closed TattdCodeMonkey closed 6 years ago
So, to make this work, my initial idea was to have a few structs like these to fit the different CRC models (code is incomplete, but should show the path I was thinking of):
typedef struct crc_params_s {
ERL_NIF_TERM key;
void *table;
uint8_t width;
uint64_t poly;
uint64_t init;
bool refin;
bool refout;
uint64_t xorout;
uint64_t check;
uint64_t residue;
char name[256];
} crc_params_t;
typedef struct crc_function_s {
int init(const void *params, void **context);
int fastupdate(void *context, const unsigned char *buf, size_t len);
int update(const void *old_context, void **new_context, const unsigned char *buf, size_t len);
int final(const void *context, ErlNifEnv *env, ERL_NIF_TERM *out_term);
} crc_function_t;
typedef struct crc_context_s {
const crc_params_t *params;
uint64_t value;
} crc_context_t;
int
crc_init(const void *params, void **context)
{
crc_context_t *c = (void *)enif_alloc_resource(crc_resource_type, sizeof(*c));
if (c == NULL) {
return -1;
}
c->params = (const crc_params_t *)params;
c->value = c->params->init;
*context = (void *)c;
return 0;
}
int
crc_fastupdate(void *context, const unsigned char *buf, size_t len)
{
crc_context_t *c = (void *)context;
uint64_t val = c->value;
if (c->params->table != NULL) {
while (len--) {
val = (val >> 8) ^ c->params->table[(val ^ (uint8_t)*buf++) & 0xFF];
}
c->value = val;
} else {
// the slower calculation here
}
return 0;
}
int
crc_update(const void *old_context, void **new_context, const unsigned char *buf, size_t len)
{
const crc_context_t *old_c = (const void *)old_context;
crc_context_t *new_c = (void *)enif_alloc_resource(crc_resource_type, sizeof(*new_c));
if (new_c == NULL) {
return -1;
}
(void)memcpy(new_c, old_c, sizeof(*new_c));
int retval = crc_fastupdate(new_c, buf, len);
if (retval != 0) {
(void)enif_release_resource((void *)new_c);
return retval;
}
*new_context = (void *)new_c;
return 0;
}
int
crc_final(const void *context, ErlNifEnv *env, ERL_NIF_TERM *out_term)
{
const crc_context_t *c = (const void *)context;
// reflect out or xorout if necessary
*out_term = enif_make_uint(env, c->value);
return 0;
}
The reason I kept the context
as void *
is due to "not really CRC" functions like CRC-16/SICK.
Also, the difference between update
and fastupdate
is for immutable versus mutable operations on a context. To mirror how crypto works, crc_update/2
should return a new reference and leave the old one untouched. However, if we're slicing the input into multiple yields, we can get away with modifying the context in-place until it has been returned to the caller. In other words: once a reference has been returned to the caller, it probably should be considered immutable.
What do you think of that direction?
If I'm following this correctly we would just define params
for the different CRC specs (CCITT, Koopman etc) But we could also support building custom ones given the param values width
polynomial
initial_value
final_xor
, reflect_in
reflect_out
. So it could support compiled tables or build them when params are created, right?
Initially creating params at runtime wouldn't even be necessary, we could just have them predefined for all the current supported versions.
So it could support compiled tables or build them when params are created, right?
Yes, so here's what one of the params definitions currently looks like in some of the local code:
static crc_params_t crc_8_params = {
{0, CRC_MODEL_TYPE_NORMAL},
NULL,
8, 0x07, 0x00, false, false, 0x00, 0xf4, 0x00,
"CRC-8"
};
The 0
at the beginning will get replaced with enif_make_atom(env, "crc_8")
, so that we can lookup the params by key (which would be :crc_8
in this case). Otherwise, the params are validated and we could potentially generate a lookup table or just perform a bit-by-bit operation on the fly. Depending on the size of the input, it might make sense to do bit-by-bit or table generation (for example, if the input is less than 256 bytes, table generation might be too expensive).
The NULL
is where the statically generated table will wind up going, but I've left it out while getting the structure nailed down.
The names and structure of things will probably change as I'm not entirely sure if every CRC algorithm out there can be defined solely with those parameters. I know SICK, for example, is abnormal and there may be others. I'll try to have the :crc_8
example pushed up by this evening on the single
branch.
I just pushed b2577a483f4408fcbe42a2f4dfd8f52607e085b1, which is a little messy, but has an initial implementation of crc_init/1
, crc_info/1
, and crc_list/0
.
Here's some example usage:
iex> :crc_nif.crc_list()
[:crc_8]
iex> context = :crc_nif.crc_init(:crc_8)
#Reference<0.4190754784.2412904449.77503>
iex> :crc_nif.crc_info(context)
%{check: 244, init: 0, key: :crc_8, name: "CRC-8", poly: 7, refin: false,
refout: false, residue: 0, type: :normal, width: 8, xorout: 0}
It also supports loading from a tuple:
iex> # These params match CRC-8:
iex> context = :crc_nif.crc_init({8, 0x07, 0x00, false, false, 0x00, 0xf4, 0x00})
#Reference<0.4190754784.2412904449.77528>
iex> :crc_nif.crc_info(context)
%{check: 244, init: 0, key: :crc_8, name: "CRC-8", poly: 7, refin: false,
refout: false, residue: 0, type: :normal, width: 8, xorout: 0}
iex> # These params *do not* match CRC-8:
iex> context = :crc_nif.crc_init({8, 0x07, 0xff, false, false, 0x00, 0xf4, 0x00})
#Reference<0.4190754784.2412904451.78229>
iex> :crc_nif.crc_info(context)
%{check: 244, init: 255, key: nil, name: nil, poly: 7, refin: false,
refout: false, residue: 0, type: :normal, width: 8, xorout: 0}
Notice in the last example that the :key
and :name
are nil
since it didn't match any known models.
You can also pass a map (like the one returned from crc_info/1
) or another reference and it will return a context based on whatever was passed:
iex> context1 = :crc_nif.crc_init(:crc_8)
#Reference<0.4190754784.2412904451.78246>
iex> info1 = :crc_nif.crc_info(context1)
%{check: 244, init: 0, key: :crc_8, name: "CRC-8", poly: 7, refin: false,
refout: false, residue: 0, type: :normal, width: 8, xorout: 0}
iex> # Pass a map:
iex> context2 = :crc_nif.crc_init(info1)
#Reference<0.4190754784.2412904451.78263>
iex> # Pass a reference:
iex> context3 = :crc_nif.crc_init(context2)
#Reference<0.4190754784.2412904451.78272>
iex> # All of them are the same:
iex> (info1 == :crc_nif.crc_info(context2)) and (info1 == :crc_nif.crc_info(context3))
true
I'm using khash.h
for the lookup table to match atom keys to pointers of the model definitions. There might be a better way to accomplish the same thing, though.
As far as the table generation goes, it might make sense to have something similar to :binary.compile_pattern/1
. Maybe something like crc_compile/1
which can generate the table for non-standard parameters. Otherwise it can just use the slower bit-by-bit strategy.
Most of the interesting stuff is in crc_model.h
and crc_model.c
, while crc_nif.c
shouldn't really need to change much once we get the layout of everything else nailed down. Rephrase: adding new models should only mean messing with crc_model.c
instead of multiple locations.
That sounds good and I agree about building the table for larger inputs vs bit-by-bit for smaller ones in general cases.
The use case I originally created this library for was validating messages from a serial device and had to calculate the CRC for every message received over a serial port. In that case even if the particular binary is small the volume of checks could warrant doing as much up front or at compile time as possible.
The use case I originally created this library for was validating messages from a serial device and had to calculate the CRC for every message received over a serial port.
I wound up doing something similar while helping a local robotics competition team and published erlang-serial_framing_protocol which also uses CRC-16/CCITT...ish (again, who knows whether there's an actual standard with a name attached to whatever it's doing). An example usage with Nerves.UART can be seen in Vex.Robot.NervesSocket (or Vex.Robot.UdpSocket which I use for development and just have Nerves forward the raw serial data over UDP).
It might be overkill, but I thought it might be fun to have the library as generic as possible for others to use. I've started playing around with integrating some third party/proprietary sensors which use some weird variations of CRC's out there and anything in C (table or not) will be faster than the pure Erlang/Elixir implementation I currently have. There are also some CRC algorithms out there (like CRC-16/SICK) which violate the rules followed by most other CRC algorithms. By refactoring the code path to be as generic as possible, when new algorithms are added as requested by others (for example, folks requesting CRC-32C), it should hopefully be as simple as adding a few lines that involve the parameter setup and static look up table.
it should hopefully be as simple as adding a few lines that involve the parameter setup and static look up table.
That sounds great to me.
I just pushed up 1c6c2cca7ea14ab5f15b1aa3d4d63e1ed9f576d3 which implements rough versions of :crc_nif.crc_update/2
and :crc_nif.crc_final/1
. There are still some problems with reflecting on some of the algorithms (in other words, the "final" function needs to be tweaked), but it currently has these implemented:
iex> :crc_nif.crc_list() |> Map.keys()
[:crc_16, :crc_16_aug_ccitt, :crc_16_ccitt, :crc_16_ccitt_false, :crc_16_dnp,
:crc_16_modbus, :crc_16_sick, :crc_16_xmodem, :crc_32, :crc_32c, :crc_64,
:crc_8]
It also supports the following as aliases of the main ones listed above:
iex> :crc_nif.crc_list()
%{crc_16: %{arc: "ARC", crc_16: "CRC-16", crc_16_arc: "CRC-16/ARC",
crc_16_lha: "CRC-16/LHA", crc_ibm: "CRC-IBM"},
crc_16_aug_ccitt: %{crc_16_aug_ccitt: "CRC-16/AUG-CCITT",
crc_16_spi_fujitsu: "CRC-16/SPI-FUJITSU"},
crc_16_ccitt: %{crc_16_ccitt: "CRC-16/CCITT",
crc_16_ccitt_true: "CRC-16/CCITT-TRUE", crc_16_kermit: "CRC-16/KERMIT",
crc_ccitt: "CRC-CCITT", kermit: "KERMIT"},
crc_16_ccitt_false: %{crc_16_ccitt_false: "CRC-16/CCITT-FALSE"},
crc_16_dnp: %{crc_16_dnp: "CRC-16/DNP"},
crc_16_modbus: %{crc_16_modbus: "CRC-16/MODBUS", modbus: "MODBUS"},
crc_16_sick: %{crc_16_sick: "CRC-16/SICK", sick: "SICK"},
crc_16_xmodem: %{crc_16_acorn: "CRC-16/ACORN", crc_16_lte: "CRC-16/LTE",
crc_16_xmodem: "CRC-16/XMODEM", xmodem: "XMODEM", zmodem: "ZMODEM"},
crc_32: %{crc_32: "CRC-32", crc_32_adccp: "CRC-32/ADCCP", pkzip: "PKZIP"},
crc_32c: %{crc_32_castagnoli: "CRC-32/CASTAGNOLI",
crc_32_interlaken: "CRC-32/INTERLAKEN", crc_32_iscsi: "CRC-32/ISCSI",
crc_32c: "CRC-32C"},
crc_64: %{crc_64: "CRC-64", crc_64_ecma_182: "CRC-64/ECMA-182"},
crc_8: %{crc_8: "CRC-8"}}
I also temporarily added CRC.generate/1
to assist with generating the static C tables.
For example, the CRC-32C table was generated with:
CRC.generate({false, 32, 0x1edc6f41, 0xffffffff, true, true, 0xffffffff, 0xe3069283, 0xb798b438})
I have left any existing implementations untouched so we can hopefully compare them and see if there are any errors or performance issues. Unless the model is a variation of SICK (currently only works in 16-bit), any custom CRC has its table generated upon initialization.
Child references have a pointer to their parent that only gets released when they are destroyed. So, something like this results in only 1 table compilation (using CRC-8/BLUETOOTH as an example):
# width=8 poly=0xa7 init=0x00 refin=true refout=true xorout=0x00 check=0x26 residue=0x00 name="CRC-8/BLUETOOTH"
crc1 = :crc_nif.crc_init({false, 8, 0xa7, 0x00, true, true, 0x00, 0x26, 0x00})
crc2 = :crc_nif.crc_init(crc1)
So the table created for crc1
will exist for its own lifetime as well as the lifetime of crc2
. You could then do something like this to do the actual calculation (since reflection is still messed up, these answers might be wrong):
iex> :crc_nif.crc(crc1, "test")
91
iex> :crc_nif.crc(crc2, "test")
91
:crc_nif.crc_info/1
also spits out more information now:
iex> :crc_nif.crc_info(:crc_nif.crc_init(:crc_16))
%{bits: 16, check: 47933, init: 0,
name: %{arc: "ARC", crc_16: "CRC-16", crc_16_arc: "CRC-16/ARC",
crc_16_lha: "CRC-16/LHA", crc_ibm: "CRC-IBM"}, poly: 32773, refin: true,
refout: true, residue: 0, root_key: :crc_16, sick: false, value: 0, width: 16,
xorout: 0}
There's also :crc_nif.debug_table/1
which spits out the generated lookup table:
iex> # Using our CRC-8/BLUETOOTH example from earlier:
iex> :crc_nif.debug_table(crc1)
{true,
[0, 107, 214, 189, 103, 12, 177, 218, 206, 165, 24, 115, 169, 194, 127, 20, 87,
60, 129, 234, 48, 91, 230, 141, 153, 242, 79, 36, 254, 149, 40, 67, 174, 197,
120, 19, 201, 162, 31, 116, 96, 11, 182, 221, 7, 108, 209, 186, 249, ...]}
check
and residue
verificationNaming of things isn't completely nailed down yet.
For example, the CCITT
implementation we had is actually a false CCITT
known as CRC-16/CCITT-FALSE
. KERMIT
is actually true CCITT
.
Also, ccitt_16_1D0F
is also known as CRC-16/AUG-CCITT
.
I think I'm done with any major code moving on the single branch.
iex> CRC.crc(:crc_16, "123456789")
47933
iex> resource = CRC.crc_init(:crc_16)
#Reference<0.48424898.781582343.49514>
iex> resource = CRC.crc_update(resource, "12345")
#Reference<0.48424898.781582343.49524>
iex> resource = CRC.crc_update(resource, "6789")
#Reference<0.48424898.781582343.49532>
iex> CRC.crc_final(resource)
47933
Here's an update on the work-in-progress list from above:
The final functions need to reflect values correctly.
Reflection is now working correctly for both the fast and slow implementation.
check
and residue
verification
Finally got the residue calculation working. Checks and residues can be verified with the :crc_algorithm
module.
For example, :crc_algorithm.verify_check(:crc_fast)
will verify that all of the predefined models calculate the predefined check value when fed the "123456789"
string.
There are 3 implementations that can be checked: :crc_fast
, :crc_pure
, and :crc_slow
. The :crc_pure
module is written entirely in Erlang and is mostly used to sanity check the C code. It's also able to do CRC calculations larger than 64 bits (like CRC-82/DARC).
SICK is so "not really CRC" it might make sense to just have it as a separate function instead of being lumped in with all of the other CRC functions.
The code is much cleaner now, so this isn't as huge a concern to me. I wish I could find out more information about SICK and whether there is a 8, 32, or 64 bit version.
Naming of things isn't completely nailed down yet.
The naming of things can still change, but it's much more uniform now.
Reliable testing/verification of algorithms using another tool. pycrc is a possible candidate, or at least the C code generated by pycrc.
I've tried to compare this implementation to pycrc and CRC RevEng as much as possible.
I wrote ~10 property tests that compare the new implementation to the old ones. CRC-16/DNP is the only one that doesn't match, but I think that's due to a reflection problem in the old implementation.
All 3 modules are verified in the tests for check and residue values.
I wrote a property test for known models as well as unknown models (and a SICK-based property test). In all of these property tests :crc_fast
, :crc_pure
, and :crc_slow
are compared against each other.
I also added CRC.Model
temporarily to help import the model definitions and generate part of the C code.
It can decode a text file with lines like this:
width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926 residue=0xdebb20e3 name="CRC-32" alias="CRC-32/ADCCP" alias="PKZIP"
I'm probably forgetting something else important, but that's the general overview.
My original intention wasn't to add all of these CRC models, but I realized as I added more and more it helped uncover any issues with the underlying implementation. There are 103 unique models predefined and 148 including aliases. Here's the full list: https://gist.github.com/potatosalad/32d31c14390d33d20c0268f6b68e22d1.
What do you think of the changes?
This is all looking great.
What do you think about combining CRC.crc_update
& crc_final
into a crc/2
that takes the resource?
In addition to 👇 :
iex> CRC.crc(:crc_16, "123456789")
47933
iex> resource = CRC.crc_init(:crc_16)
#Reference<0.48424898.781582343.49514>
iex> resource = CRC.crc_update(resource, "12345")
#Reference<0.48424898.781582343.49524>
iex> resource = CRC.crc_update(resource, "6789")
#Reference<0.48424898.781582343.49532>
iex> CRC.crc_final(resource)
47933
could we do👇 as well?
iex> CRC.crc(:crc_16, "123456789")
47933
iex> resource = CRC.crc_init(:crc_16)
#Reference<0.48424898.781582343.49514>
iex>CRC.crc(resource, "123456789")
47933
Would that make sense?
resource
like that?CRC.crc_16/1
that uses the specific implementation NIF file?resource
when initializing a GenServer
and re-using it for the life of the process?Along with the second questions I'm wondering what the differences would be between:
iex> CRC.crc(:crc_16, "123456789")
47933
iex> resource = CRC.crc_init(:crc_16)
#Reference<0.48424898.781582343.49514>
iex> resource = CRC.crc_update(resource, "12345")
#Reference<0.48424898.781582343.49524>
iex> resource = CRC.crc_update(resource, "6789")
#Reference<0.48424898.781582343.49532>
iex> CRC.crc_final(resource)
47933
iex> CRC.crc_16("123456789")
47933
could we do👇 as well?
iex> CRC.crc(:crc_16, "123456789") 47933 iex> resource = CRC.crc_init(:crc_16) #Reference<0.48424898.781582343.49514> iex>CRC.crc(resource, "123456789") 47933
Yup, that actually works exactly like that right now. Passing a resource to CRC.crc/2
or CRC.crc_init/1
will either (1) create a new resource pointing to the predefined model or (2) create a new reference with a pointer to the parent resource's already compiled table.
For example, if I wanted to create a new resource based on an undefined CRC model:
iex> my_model = %{init: 0, poly: 27, refin: true, refout: true, width: 64, xorout: 0}
%{init: 0, poly: 27, refin: true, refout: true, width: 64, xorout: 0}
iex> CRC.crc(my_model, "123456789")
5090661014116757502
The only problem is that it's fairly inefficient to recompile the lookup table every time. By first converting the model into a resource, the lookup table is only compiled once.
iex> my_resource = CRC.crc_init(my_model)
#Reference<0.205264752.3201695745.69200>
iex> CRC.crc(my_resource, "123456789")
5090661014116757502
Check out the benchmark comparison:
iex> map_example = fn (input) -> CRC.crc(my_model, input) end
#Function<6.99386804/1 in :erl_eval.expr/5>
iex> res_example = fn (input) -> CRC.crc(my_resource, input) end
#Function<6.99386804/1 in :erl_eval.expr/5>
iex> :crc_bench.compare([map: map_example, res: res_example], ["123456789"], 1000)
[map: %{reds: %{acc: 121086, avg: 121.086, max: 203, min: 120},
time: %{acc: 13487000, avg: 13487.0, max: 66000, min: 10000}},
res: %{reds: %{acc: 121016, avg: 121.016, max: 126, min: 120},
time: %{acc: 1950000, avg: 1950.0, max: 8000, min: 1000}}]
So the map based calculation took ~14µs and the resource based calculation took ~2µs. That's not a huge difference, but could have an impact for lots of tiny calculations on small-ish binary data. Also note that the max time taken was ~70µs versus ~8µs.
- Is there a benefit to re-using the
resource
like that?
Yes, it's much faster for non-predefined CRC's and slightly faster for atom-based CRC's (instead of having to do a hash table lookup based on the atom, it can just re-use the pointer of the parent resource). The "slightly faster" probably isn't worth not using an atom, however.
- How would it differ from using
CRC.crc_16/1
that uses the specific implementation NIF file?
Input/output-wise, they should both be identical. Internally, the new implementation is able to shove all of the CRC calculations through the same generic function with the defined model (width, poly, init, refin, refout, xorout) and it will produce the result. The alternative is what was happening before where every new model required adding new NIF functions and its own implementation.
Technically, CRC.crc_16/1
could just be rewritten as:
def crc_16(input) do
CRC.crc(:crc_16, input)
end
- Would it be advisable to create the
resource
when initializing aGenServer
and re-using it for the life of the process?
Yes, that was my thought as well. The resource will live as long as the process does. Technically, the resource can also be passed to other processes which will keep it alive for longer. Once the last process referencing the resource either no longer references it or dies, the resource will be garbage collected.
You might also be able to store a resource in ets...I didn't think that would work, but I just tried it locally and it seems to have worked.
Quick note on the implementation details for CRC-16:
All that was required to add support for CRC-16 was to add a few lines in two locations of the same file:
crc_model_uint16.c.h#L35-L40
crc_model_uint16.c.h#L530-L558
Let's say there's another model you want to add, like this crazy reflected version of CRC-8/AUTOSAR (I just changed refin and refout to true, which also changes the check value):
width=8 poly=0x2f init=0xff refin=true refout=true xorout=0xff check=0xc4 residue=0x42 name="CRC-8/AUTOSAR-REFLECTED"
Here's where I wrote CRC.Model
to help with the code/table generation:
iex> {:ok, model, <<>>} = CRC.Model.decode(~S[width=8 poly=0x2f init=0xff refin=true refout=true xorout=0xff check=0xc4 residue=0x42 name="CRC-8/AUTOSAR-REFLECTED"])
{:ok,
%CRC.Model{aliases: %{}, bits: 8, check: 196, init: 255,
key: :crc_8_autosar_reflected, name: "CRC-8/AUTOSAR-REFLECTED", poly: 47,
refin: true, refout: true, residue: 66, sick: false, slow: false, value: 0,
width: 8, xorout: 255}, ""}
iex> CRC.Model.dump_code([model])
# /* crc_8_autosar_reflected */
# {{NULL, NULL}, false, 0, "crc_8_autosar_reflected", 0, "crc_8_autosar_reflected", "CRC-8/AUTOSAR-REFLECTED"},
#
# /* width=8 poly=0x2f init=0xff refin=true refout=true xorout=0xff check=0xc4 residue=0x42 name="CRC-8/AUTOSAR-REFLECTED" */
# {{{NULL, NULL}, true, 0, "crc_8_autosar_reflected", 8},
# false,
# 8,
# 0x2f,
# 0xff,
# true,
# true,
# 0xff,
# 0xc4,
# 0x42,
# {0x00,0xc7,0x67,0xa0,0xce,0x09,0xa9,0x6e,0x75,0xb2,0x12,0xd5,0xbb,0x7c,0xdc,0x1b,0xea,0x2d,0x8d,0x4a,0x24,0xe3,0x43,0x84,0x9f,0x58,0xf8,0x3f,0x51,0x96,0x36,0xf1,0x3d,0xfa,0x5a,0x9d,0xf3,0x34,0x94,0x53,0x48,0x8f,0x2f,0xe8,0x86,0x41,0xe1,0x26,0xd7,0x10,0xb0,0x77,0x19,0xde,0x7e,0xb9,0xa2,0x65,0xc5,0x02,0x6c,0xab,0x0b,0xcc,0x7a,0xbd,0x1d,0xda,0xb4,0x73,0xd3,0x14,0x0f,0xc8,0x68,0xaf,0xc1,0x06,0xa6,0x61,0x90,0x57,0xf7,0x30,0x5e,0x99,0x39,0xfe,0xe5,0x22,0x82,0x45,0x2b,0xec,0x4c,0x8b,0x47,0x80,0x20,0xe7,0x89,0x4e,0xee,0x29,0x32,0xf5,0x55,0x92,0xfc,0x3b,0x9b,0x5c,0xad,0x6a,0xca,0x0d,0x63,0xa4,0x04,0xc3,0xd8,0x1f,0xbf,0x78,0x16,0xd1,0x71,0xb6,0xf4,0x33,0x93,0x54,0x3a,0xfd,0x5d,0x9a,0x81,0x46,0xe6,0x21,0x4f,0x88,0x28,0xef,0x1e,0xd9,0x79,0xbe,0xd0,0x17,0xb7,0x70,0x6b,0xac,0x0c,0xcb,0xa5,0x62,0xc2,0x05,0xc9,0x0e,0xae,0x69,0x07,0xc0,0x60,0xa7,0xbc,0x7b,0xdb,0x1c,0x72,0xb5,0x15,0xd2,0x23,0xe4,0x44,0x83,0xed,0x2a,0x8a,0x4d,0x56,0x91,0x31,0xf6,0x98,0x5f,0xff,0x38,0x8e,0x49,0xe9,0x2e,0x40,0x87,0x27,0xe0,0xfb,0x3c,0x9c,0x5b,0x35,0xf2,0x52,0x95,0x64,0xa3,0x03,0xc4,0xaa,0x6d,0xcd,0x0a,0x11,0xd6,0x76,0xb1,0xdf,0x18,0xb8,0x7f,0xb3,0x74,0xd4,0x13,0x7d,0xba,0x1a,0xdd,0xc6,0x01,0xa1,0x66,0x08,0xcf,0x6f,0xa8,0x59,0x9e,0x3e,0xf9,0x97,0x50,0xf0,0x37,0x2c,0xeb,0x4b,0x8c,0xe2,0x25,0x85,0x42}},
:ok
Copy and paste those two sections into crc_model_uint8.c.h
and you'll then be able to do:
iex> CRC.crc(:crc_8_autosar_reflected, "123456789")
196
Also, the C code can be nicely formatted again by running make clang-format-all
from the c_src
directory.
The max size for a name or key in the above examples is 31 characters (31 + '\0'
). Most of the names never reach larger than ~20 characters.
Whoops, I just realized I never answered your last question (which I've broken into 3 sections):
CRC.crc/2
work?Along with the second questions I'm wondering what the differences would be between:
iex> CRC.crc(:crc_16, "123456789") 47933
This calls :crc_nif.crc_fast/2
which calls crc_nif_crc_fast_2
on the C side of things.
Internally, it calls crc_init
which accepts either an atom, map, tuple, or reference and attempts to derive a model (either pre-defined or in-memory). A resource is then created with crc_resource_create
which either creates:
After the resource has been created and since it will never be returned to the caller, we can simply use it to make modifications in-place instead of treating it as immutable. The next step is to either:
crc_resource_update_unsafe
and crc_resource_final
if the size of the input is less than or equal to XNIF_SLICE_MAX_PER_SLICE
(~20KB)xnif_slice_schedule
and loop/yield until all of the input has been processedSo really, this just does the C version of calling CRC.crc_init/1
, CRC.crc_update/2
, and CRC.crc_final/1
in sequence.
CRC.crc_init/1
, CRC.crc_update/2
, and CRC.crc_final/1
work?iex> resource = CRC.crc_init(:crc_16) #Reference<0.48424898.781582343.49514> iex> resource = CRC.crc_update(resource, "12345") #Reference<0.48424898.781582343.49524> iex> resource = CRC.crc_update(resource, "6789") #Reference<0.48424898.781582343.49532> iex> CRC.crc_final(resource) 47933
This is the same as the first case, except that the resource is returned to the caller and is therefore immutable.
So calling :crc_nif.crc_fast_update/2
actually calls crc_nif_crc_fast_update_2
which calls crc_resource_update
. This makes a clone of the existing resource (which contains the model pointer and state/value of the calculation) and then calls crc_resource_update_unsafe
with the freshly cloned resource. After this point, the new resource is returned to the caller and is considered immutable.
The state is kept "unfinished" until :crc_nif.crc_fast_final/1
is called which again clones the resource and performs the final calculation. The cloned resource is then released/discarded and only the resulting value is returned to the caller.
So, technically, you can re-use an old resource if you wanted to pick up in the middle of a calculation:
iex> r0 = CRC.crc_init(:crc_16)
#Reference<0.205264752.3201695745.76917>
iex> r1 = CRC.crc_update(r0, "12345")
#Reference<0.205264752.3201695745.76925>
iex> r2a = CRC.crc_update(r1, "6789")
#Reference<0.205264752.3201695745.76933>
iex> r2b = CRC.crc_update(r1, "9876")
#Reference<0.205264752.3201695745.76941>
iex> CRC.crc_final(r2a)
47933
iex> CRC.crc_final(r2b)
22603
iex> # Let's make sure they match the one-shot version:
iex> CRC.crc(:crc_16, "123456789")
47933
iex> CRC.crc(:crc_16, "123459876")
22603
CRC.crc_16/1
work?iex> CRC.crc_16("123456789") 47933
This is much simpler and doesn't involve any resource creation, it simply returns an unsigned integer to the caller directly.
The entire definition can be found in crc_16.c
and has a lot of duplicated code from the other functions. It's also slightly slower for larger binaries:
iex> :crc_bench.compare([old: fn (input) -> CRC.crc_16(input) end, new: fn (input) -> CRC.crc(:crc_16, input) end], [:binary.copy("123456789", 1024 * 10)], 1000)
[old: %{reds: %{acc: 8108792, avg: 8108.792, max: 14801, min: 8081},
time: %{acc: 1369085000, avg: 1369085.0, max: 2947000, min: 1299000}},
new: %{reds: %{acc: 1618905, avg: 1618.905, max: 3736, min: 1536},
time: %{acc: 235386000, avg: 235386.0, max: 535000, min: 222000}}]
So for ~100KB input, the old implementation takes ~1500µs and the new implementation takes ~250µs. For smaller binaries, both implementations are about the same speed-wise.
Alright, I'm done being waaaay too wordy now, hopefully some of those comments made sense :smile:
I lied.
All of the normal CRC models hold only the current "value" (a single unsigned integer) as their state. CRC-16/SICK (or just SICK), however, breaks the rules and actually holds two pieces of information as its "state" while calculating. The first is the current "value" and the second is the last received byte from the last input.
You can debug the current value/state with :crc_nif.crc_info/1
(or using the :crc_fast
module as shown):
iex> crc_16 = :crc_fast.init(:crc_16)
#Reference<0.205264752.3201957889.130564>
iex> crc_16 = :crc_fast.update(crc_16, "123456789")
#Reference<0.205264752.3201957889.130573>
iex> :crc_fast.info(crc_16)
%{aliases: %{arc: "ARC", crc_16: "CRC-16", crc_16_arc: "CRC-16/ARC",
crc_16_lha: "CRC-16/LHA", crc_ibm: "CRC-IBM"}, bits: 16, check: 47933,
init: 0, key: :crc_16, name: <<192, 6, 128, 7, 65, 199>>, poly: 32773,
refin: true, refout: true, residue: 0, sick: false, slow: false, value: 48349,
width: 16, xorout: 0}
iex> :crc_fast.final(crc_16)
47933
CRC-16/SICK technically uses the same poly, init, and xorout as CRC-16 (also refin and refout are kind of the same), but the actual calculation is very different:
iex> sick = :crc_fast.init(:sick)
#Reference<0.205264752.3201957889.130564>
iex> sick = :crc_fast.update(sick, "123456789")
#Reference<0.205264752.3201957889.130573>
iex> :crc_fast.info(sick)
%{aliases: %{crc_16_sick: "CRC-16/SICK", sick: "SICK"}, bits: 16, check: 22182,
init: 0, key: :crc_16_sick, name: nil, poly: 32773, refin: false,
refout: false, residue: 0, sick: true, slow: false, value: 42582, width: 16,
xorout: 0}
iex> :crc_fast.final(sick)
22182
So, for CRC-16 between the value after update and final being called:
48349 ->
47933
0xbcdd ->
0xbb3d
0b10111100_11011101 ->
0b10111011_00111101
All of the bits were essentially reflected/reversed.
For SICK, however:
42582 ->
22182
0xa656 ->
0x56a6
0b10100110_01010110 ->
0b01010110_10100110
Only the bytes have been reflected/reversed.
Right now there's only a 16-bit implementation for SICK in crc_algorithm_sick.c.h
. Any other bit-size will fail. There's probably some way to generalize the algorithm for other bit-sizes, but I'm not sure how or if that would even be useful to anyone.
Okay, now I'm done :smile:
Thanks for the thorough explanations, I just wanted to make sure I was following along accurately. This all looks amazing.
I really like the simplified implementation of the crc_
functions and the easy of extension. It also making me rethink supporting the current individual functions for all the different versions.
If I do want to keep them around then I could likely automate their definitions to a macro, but even that seems a bit overkill. The other option would be to refactor them to call :crc.crc/2
but add deprecation workings. release a v0.9
then remove them in v1
. The would reduce the surface area of the library from a maintenance perspective, but obviously be a breaking-change. but CRC.ccitt_16(input)
to CRC.crc(:crc_16_ccitt_false, input)
would be a relatively minor change overall.
I'm going to think on that before making any decisions right way, your thoughts?
I really can't thank you enough for all this work. It is way more than I could of ever done on my own.
If you did want to eventually drop them, I think the deprecation warnings could work for a v0.9
to v1
transition.
There are 3 incompatibilities that I know of:
CRC.crc_8("123456789")
does not match CRC.crc(:crc_8_koop, "123456789")
.
This is due to the initial value being set to 0x00
in the old implementation when it really should have been set to 0xff
(the old one XOR's the seed, so 0xff ^ 0xff = 0x00
).
However, CRC.crc_8("123456789", 0x00)
does match the new implementation.
CRC.crc_16_dnp("123456789")
does not match CRC.crc(:crc_16_dnp, "123456789")
.
They both technically produce the same number, but they're just byte-mirror images of each other (old produces 0x82ea
and new produces 0xea82
).
CRC RevEng CRC-16/DNP shows 0xea82
as the check value, while the On-line CRC calculator shows 0x82ea
.
Command line tools also flip the output:
./pycrc.py --model=crc-16-dnp --check-string="123456789"
# => 0xea82
./reveng -c -m CRC-16/DNP 313233343536373839
# => 0x82ea
So...who knows? Flipping the output would break the rules (from my understanding) in the same way that SICK handles things. I can't find a ton of information about anything published for CRC-16/DNP, so my guess is just to go with the new 0xea82
version since it follows the same pattern as all other models.
The only other use-case I can think of that might still exist is for anyone who is using a different "seed" or "init" to an otherwise standard CRC.
For example, someone doing something like this:
iex> CRC.ccitt_16("123456789", 0xabcd)
28675
They would now have to do something like this:
iex> CRC.crc(%{width: 16, poly: 0x1021, init: 0xabcd, refin: false, refout: false, xorout 0x0000}, "123456789")
28675
Maybe having some sort of "extend" syntax might help bridge the gap:
iex> CRC.crc(%{extend: :crc_16_ccitt_false, init: 0xabcd}, "123456789")
28675
Then again, if nobody is using that feature right now it might also be okay if it gets dropped.
An additional comment on the CRC-16/DNP thing: there might be an additional variable missing from the calculations: endian. Something like endian=little
and we could potentially flip the endianness of the result. However, I'm not sure if that might break other models as a result.
For 2. I saw that with #10 as well, in that case it was a matter of Kermit requiring little endian. and one of the online calculators I was using for testing not adhering to that.
Oh okay, that makes sense. I'm also not sure whether this library might have problems on a big-endian system or not. Also, whether 32-bit systems will be able to run everything correctly.
Yea it likely depends on the specs, some require little endian. most x64 stuff is big endian (right?). If its ever an issue the result can be swapped by the end-user.
I used to run into this pretty often in the past where I was integrating lots of different hardware.
I just pushed up a small commit that adds support for extending another model, so the example from earlier actually works now:
iex> CRC.crc(%{extend: :crc_16_ccitt_false, init: 0xabcd}, "123456789")
28675
The :extend
value can be anything that you would normally pass to CRC.crc/2
or CRC.crc_init/1
. So an atom, 6-arity map, 9-arity tuple, or a reference to an existing CRC resource.
Another quick commit that fixes the name field when calling :crc_nif.crc_info/1
.
It also adds two property tests that can run against CRC RevEng and pycrc if they are installed.
For example:
$ export PYCRC_BIN=~/Downloads/pycrc-0.9.1/pycrc.py
$ export REVENG_BIN=~/Downloads/reveng-1.5.2/reveng
$ mix test
make: Nothing to be done for 'all'.
..............................................
Finished in 7.0 seconds
19 properties, 27 tests, 0 failures
Randomized with seed 481923
There's probably some fiddling that could be done with travis so those tests run automatically, but I haven't messed with it yet.
@potatosalad just want to drop a line to say I haven't forgot about this, my work & home life has been a bit hectic so I haven't been able to carve out time to spend on working through it yet. I might get lucky and get to steal some time during the holiday next week to spend a hour or two and get a new release together.
@TattdCodeMonkey It's all good. I've been traveling a bunch lately and dealing with a move, so I've also been short on time. Let me know if you want any changes made, code cleaned up, or if you have any questions at all. I should have a little down time during the holiday as well.
@potatosalad I'm thinking about writing some simple docs for CRC.crc
then merging single
branch and doing a v0.8
release before unifying all the existing functions to utilize the single crc function. Thoughts?
That would let it be out in the wild a bit and give some time to work on moving towards using the single function for all the other built-ins and consolidating the NIFs down.
Merged the single
branch and released v0.8 today. But I still have some outstanding things I want to do, but I'll create some new issues for those and close this one. @potatosalad thanks so much for your work in here I really appreciate it.
Initially discussed in #11 under
Possible Improvements
implementingcrc/2
,crc_init/1
,crc_update/2
, andcrc_final/1
will allow implementing new algorithms by just passing the required params tocrc_init/1
and using the context provided with the other functions. This would allow reduction of C code to a single implementation, instead of separate files for different widths etc.