Standard CRC32 table based algorithm implemented. #32

CLomanno · 2018-04-17T14:56:21Z

I had to redefine the polys and expected CRCs for everything in CRC32. However I modified the functions in crc32 so they are all backwards compatible.

The new function new_with_initial_and_final() allows you to generate a reflected table with a custom initial and final XOR value.

@mrhooray
Sorry, this is my first pull request and I didn't add a reviewer, assignee, or label.

…in table generation and crc calculation. Maintained reverse compatability with v1.7.0 and added docs

CLomanno · 2018-04-17T14:59:27Z

I found the default values for various 32bit crc standards here: https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Polynomial_representations_of_cyclic_redundancy_checks

Verified the correct crc values here: http://crccalc.com/

CLomanno · 2018-04-18T20:27:14Z

@mrhooray
Sorry, this is my first pull request and I didn't add a reviewer, assignee, or label.

Updated my branch to 1.8.1

CLomanno · 2018-05-24T00:20:00Z

@mrhooray I completed updating all 3 CRC types. Now crc16, crc32, and crc64 are backwards compatible and can work normal or reflected.

mrhooray

thanks @CLomanno for updating the pr, left a few minor comments and gonna play around with it locally.

also added you as collaborator for this module since you care a lot about correctness, backward compatibility, users, etc

mrhooray · 2018-05-24T02:06:49Z

Cargo.toml

@@ -12,6 +12,13 @@ license = "MIT OR Apache-2.0"
 [build-dependencies]
 build_const = "0.2"

+#[dev-dependencies]


shall we remove unrelated changes or you want to move benchmarks to use criterion instead in this pr?

Criteron is nice, but we can use whatever you want. I left both in for you to choose

cool, let's remove the commented code and revisit benchmark framework in separate pr?

Removed, Criterion adds a lot of bloat. I'll save the code for later in case it needs added back in

mrhooray · 2018-05-24T02:07:07Z

benches/bench.rs

 }
+
+/*
+#[macro_use]


mrhooray · 2018-05-24T02:08:20Z

src/crc16.rs

+///
+/// *table:* Holds the table values based on the supplied polynomial for the fast CRC calculations
+///
+/// *initial:* The initial inut value. AKA reflect_in


nit: input instead of inut, and a few other occurrences in this pr

A lot of the comments were copy/pasted between crc16/32/64

do you want to keep it, or it's actually a typo?

mrhooray · 2018-05-25T04:11:49Z

src/util.rs

+}
+
+/// Reflects the lease significant byte of a u32.
+pub fn reflect_long_32(input: u32) -> u32 {


have following 3 functions named consistently like reflect_byte_16/32/64?

fixed to reflect_value_16 etc.

mrhooray · 2018-05-25T04:13:36Z

src/util.rs

    }
    table
 }
+
+/// Reflects a value of a 16 bit number
+pub fn reflect_short(mut value: u16) -> u16 {


reflect_16/32/64 or something similar?
just to make things consistent with next set of 3 functions

fixed to reflect_byte_16 etc.

nickbabcock

Sorry for the sudden influx of comments. I'm interested in seeing if I can replace code I've written with this crate, so I'd thought I'd voice my opinions 😄

nickbabcock · 2018-05-25T21:11:40Z

src/crc16.rs

    for &i in bytes.iter() {
-        value = table[((value as u8) ^ i) as usize] ^ (value >> 8)
+        if true == rfl {


The test for reflection should be hoisted outside the loop to avoid the needless conditional check for each byte. Also I feel like

if rfl { }

is more idiomatic than

if true == rfl { }

updated to just if rfl {

It makes sense to take it out of the update() function. I couldn't cleanly get it out of make_table_crcXX()

nickbabcock · 2018-05-25T21:14:29Z

src/crc16.rs

 }

 impl Digest {
+    /// *Only works for reflected CRCs*


I have you taken a look at how these docs render? If you are intending for there to be a space between this and the next sentence I believe you'll a new line, else it might just render as a single paragraph

You're right. Fixed

nickbabcock · 2018-05-25T21:16:34Z

src/crc32.rs

+///
+/// # Definitions
+///
+/// *table:* Holds the table values based on the supplied polynomial for the fast CRC calculations


You may have better luck with formatting with lists

- table: Holds the table values based on the supplied polynomial for the fast CRC calculations - initial: - reflect:

nickbabcock · 2018-05-25T21:19:42Z

src/util.rs

-pub fn make_table_crc16(poly: u16) -> [u16; 256] {
+/// Builds a CRC16 table using the standard or reflected CRC method
+/// If reflect==true, flip the individual byte bitwise, then flip the 32bit table value bitwise
+pub fn make_table_crc16(poly: u16, rfl: bool) -> [u16; 256] {


If in the rustdoc you mention the reflect parameter, shouldn't the parameter be reflect: bool instead of rfl: bool.

nickbabcock · 2018-05-25T21:51:02Z

As a side note, I benchmarked this impl against:

pub fn calc_crc(data: &[u8]) -> u32 {
    !data.iter().fold(!0xefcb_f201, |acc, &x| {
        (acc << 8) ^ (TABLE[((u32::from(x)) ^ (acc >> 24)) as usize])
    })
}

Both produce the same output (:+1:), but this PR is 10-15% slower.

For reference, I wrote:

lazy_static! {
    static ref TABLE: [u32; 256] = make_table(0x04c11db7, false);
}

pub fn calc_crc(data: &[u8]) -> u32 {
    !update(!0xefcb_f201, &TABLE, data, false)
}

CLomanno · 2018-05-30T02:34:24Z

@nickbabcock I like your speed improvement. I put it in! It also got rid of the if rfl { check per iteration

mrhooray · 2018-05-31T10:22:12Z

thanks @CLomanno @nickbabcock
will update readme etc and release

CLomanno added 2 commits April 16, 2018 11:08

FINALLY got CRC32 correct. Fixing up now

02b82ef

Updated the code in crc32 to use the standard crc32 algorithms. Both …

27311e2

…in table generation and crc calculation. Maintained reverse compatability with v1.7.0 and added docs

Cleaned up come comments and removed some temporary comments

f44dc5d

CLomanno closed this Apr 18, 2018

CLomanno reopened this Apr 18, 2018

mrhooray force-pushed the master branch from 0ccf2e3 to 5a37494 Compare April 24, 2018 08:40

CLomanno mentioned this pull request Apr 24, 2018

Custom polynomials not working because crc-rs does not implement the complete CRC32 algorithm. #31

Closed

CLomanno mentioned this pull request May 16, 2018

mpeg2 crc32 #33

Closed

CLomanno and others added 3 commits May 16, 2018 15:19

Merge branch 'master' into reflect-data

ae81e7a

Updated my branch to 1.8.1

ran cargo fmt to clean up the code

dcb2af9

Moved the benchmarks to the criterion crate

3576a01

mrhooray mentioned this pull request May 17, 2018

Bench testing no longer working in Rust 1.26 stable #34

Closed

CLomanno and others added 9 commits May 17, 2018 11:00

cleaned up formatting for criterion benchmarking

20a409d

Updated the MB benchmark to only do 991KB to prevent a stack overflow

08dc115

Changed the 1MB benchmarks to 991kB to prevent a stack overflow

9aa3464

crc64 normal started

1290f16

Updated benches for crc64

4e55cad

crc64 custom working with tests

d495811

Updated CRC16 to the new format

599a445

Added docs for CRC16

14482b4

rustfmt and cleaned up docs for CRC64

75560b0

mrhooray reviewed May 24, 2018

View reviewed changes

mrhooray reviewed May 25, 2018

View reviewed changes

nickbabcock reviewed May 25, 2018

View reviewed changes

Updated typos, docs, and standardized function names

7a85eb5

Implimented speed improvements from @nickbabcock

c0057f6

mrhooray merged commit 654d7da into mrhooray:master May 31, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Standard CRC32 table based algorithm implemented. #32

Standard CRC32 table based algorithm implemented. #32

CLomanno commented Apr 17, 2018 •

edited

CLomanno commented Apr 17, 2018

CLomanno commented Apr 18, 2018

CLomanno commented May 24, 2018

mrhooray left a comment

mrhooray May 24, 2018

CLomanno May 24, 2018

mrhooray May 25, 2018

CLomanno May 30, 2018

mrhooray May 24, 2018

CLomanno May 30, 2018

mrhooray May 24, 2018

CLomanno May 24, 2018

mrhooray May 25, 2018

mrhooray May 25, 2018

CLomanno May 30, 2018

mrhooray May 25, 2018

CLomanno May 30, 2018

nickbabcock left a comment

nickbabcock May 25, 2018

CLomanno May 30, 2018

CLomanno May 30, 2018

nickbabcock May 25, 2018

CLomanno May 30, 2018

nickbabcock May 25, 2018

CLomanno May 30, 2018 •

edited

nickbabcock May 25, 2018

CLomanno May 30, 2018

nickbabcock commented May 25, 2018

CLomanno commented May 30, 2018 •

edited

mrhooray commented May 31, 2018

Standard CRC32 table based algorithm implemented. #32

Standard CRC32 table based algorithm implemented. #32

Conversation

CLomanno commented Apr 17, 2018 • edited

CLomanno commented Apr 17, 2018

CLomanno commented Apr 18, 2018

CLomanno commented May 24, 2018

mrhooray left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

nickbabcock left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

CLomanno May 30, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

nickbabcock commented May 25, 2018

CLomanno commented May 30, 2018 • edited

mrhooray commented May 31, 2018

CLomanno commented Apr 17, 2018 •

edited

CLomanno May 30, 2018 •

edited

CLomanno commented May 30, 2018 •

edited