Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

hash/crc32: clean up logic around tables #16909

Closed
RaduBerinde opened this issue Aug 28, 2016 · 3 comments
Closed

hash/crc32: clean up logic around tables #16909

RaduBerinde opened this issue Aug 28, 2016 · 3 comments

Comments

@RaduBerinde
Copy link
Contributor

The logic around the tables in crc32 is a nightmare. It all results from the rigid API in which [256]uint32 Tables are passed around, pretty much assuming that a 256x4 table is the best and only thing needed to calculate a CRC. In the meantime, we got the optimized slicing-by-8 which needs 8 of these tables and some hardware-assisted implementations which need different tables, or need no tables at all.

Here are a few problems and inconsistencies that should be addressed:

  • when using slicing-by-8, we also compute the "old style" table, even though it is always identical to the first of the 8 tables (so we compute and store it twice)
  • when using Castagnoli, we initialize the slicing-by-8 tables on the first MakeTable; when using IEEE, we initialize it on the first use (inside updateIEEE).
  • we don't use the faster slicing-by-8 for other polynomials
  • when SSE42 is available, castagnoliTable will be nil, and thus MakeTable will return nil; nil is accepted as a valid Castagnoli table so a typical user of the API won't notice, but this is not correct (this was introduced recently in hash/crc32: use faster method for CRC32-C  #16107).

Ideally, the API should be changed so that Table is an interface or struct with unexported fields. I don't know if this can be done without compatibility implications.

@RaduBerinde
Copy link
Contributor Author

RaduBerinde commented Aug 28, 2016

Another one: the sliceBy8Cutoff optimization can and should be done internally in updateSlicingBy8, not at every call site.

@gopherbot
Copy link

CL https://golang.org/cl/27934 mentions this issue.

gopherbot pushed a commit that referenced this issue Aug 28, 2016
When SSE is available, we don't need the Table. However, it is
returned as a handle by MakeTable. Fix this to always generate
the table.

Further cleanup is discussed in #16909.

Change-Id: Ic05400d68c6b5d25073ebd962000451746137afc
Reviewed-on: https://go-review.googlesource.com/27934
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

CL https://golang.org/cl/27935 mentions this issue.

RaduBerinde added a commit to RaduBerinde/go that referenced this issue Aug 28, 2016
Major reorganization of the crc32 code:

 - The arch-specific files now implement a well-defined interface
   (documented in crc32.go). They no longer have the responsibility of
   initializing and falling back to a non-accelerated implementation;
   instead, that happens in the higher level code.

 - The non-accelerated algorithms are moved to a separate file with no
   dependencies on other code.

 - The "cutoff" optimization for slicing-by-8 is moved inside the
   algorithm itself (as opposed to every callsite).

Tests are significantly improved:
 - direct tests for the non-accelerated algorithms.
 - "cross-check" tests for arch-specific implementations (all archs).
 - tests for misaligned buffers for both IEEE and Castagnoli.

Fixes golang#16909.

Change-Id: I9b6dd83b7a57cd615eae901c0a6d61c6b8091c74
@golang golang locked and limited conversation to collaborators Aug 31, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

2 participants