Skip to content

Use faster CRC16 algorithm to speed up encoding/decoding#57

Merged
erikd merged 4 commits into
xiph:masterfrom
enzo1982:master
May 20, 2018
Merged

Use faster CRC16 algorithm to speed up encoding/decoding#57
erikd merged 4 commits into
xiph:masterfrom
enzo1982:master

Conversation

@enzo1982

Copy link
Copy Markdown
Contributor

Hi all,

This PR replaces the single look-up-table CRC16 implementation with the slicing-by-8 algorithm. The new algorithm is approximately 5 times faster than single table lookup CRC and improves FLAC encoding/decoding performance by about 5%.

The PR consists of 3 commits:

  • Commit 4ec6cf1 removes some unused CRC8 functions.
  • Commit f789008 replaces the CRC16 algorithm and speeds up encoding performance.
  • Commit f6a0d22 implements blockwise CRC updates for decoding (instead of wordwise) and speeds up decoding.

The last of the relevant patents on this algorithm expired in December 2017. The slicing algorithm is already used by zlib, the Linux kernel and other projects.

See here for my original article on this and here for the discussion on HydrogenAudio.

It would be great to see this added to the official FLAC source.

Robert

@lvqcl

lvqcl commented Apr 30, 2018

Copy link
Copy Markdown
Contributor

I make x86-64 builds of FLAC with MinGW and GCC 7.3.0.

This code passes all tests when I build it with '--host=x86_64-w64-mingw32' option, but fails with '--enable-64-bit-words --host=x86_64-w64-mingw32' option.

The last line of the output of 'make check':

[S]VP   set STREAMINFO (change sample rate)
        testing 'metadata.flac'... 0... 1... 2... content... PASSED
[S]VP   next
S[V]P   insert APPLICATION after, expand into padding of exceeding size
        testing 'metadata.flac'... 0... 1... 2... 3... content... PASSED
SV[A]P  next
SVA[P]  set APPLICATION, expand into padding of exceeding size
        testing 'metadata.flac'... 0... 1... 2... 3... 4... content... PASSED
SVA[A]P set APPLICATION (grow), don't expand into padding
        testing 'metadata.flac'... 0... 1... 2... 3... 4... content... PASSED
SVA[A]P set APPLICATION (shrink), don't fill in with padding
        testing 'metadata.flac'... 0... 1... 2... 3... 4... content... PASSED
SVA[A]P set APPLICATION (grow), expand into padding of exceeding size
        testing 'metadata.flac'... 0... 1... 2... 3... 4... content... PASSED
SVA[A]P set APPLICATION (shrink), fill in with padding
        testing 'metadata.flac'... 0... 1... 2... 3... 4... 5... content... PASSED
SVA[A]PP        next
SVAA[P]P        next
SVAAP[P]        set PADDING (shrink), don't fill in with padding
        testing 'metadata.flac'... 0... 1... 2... 3... 4... 5... content... ERROR during test_libFLAC

and test_libFLAC.exe crashes with 0xc0000005 exception.

Please investigate.

@enzo1982

Copy link
Copy Markdown
Contributor Author

Thanks for looking into this!

Indeed, there was a bug in crc16_update_block_ when no whole word had been consumed since the last update. It's more likely to happen with larger words which is why it was triggered by --enable-64-bit-words.

Should be fixed now.

@erikd

erikd commented Apr 30, 2018

Copy link
Copy Markdown
Member

This code passes all tests when I build it with '--host=x86_64-w64-mingw32' option, but fails with '--enable-64-bit-words --host=x86_64-w64-mingw32' option.

This suggests that the travis build tests are incomplete. Looking into that now.

@erikd

erikd commented Apr 30, 2018

Copy link
Copy Markdown
Member

@enzo1982 I've just updated the Travis build to include building with the option specified by @lvqcl . Would be good if you could rebase against that and see if you can reproduce the problem @lvqcl mentioned.

@enzo1982

Copy link
Copy Markdown
Contributor Author

@erikd OK, I rebased and Travis is building again. The bug found by @lvqcl should already be fixed by commit d57fb5c, so I expect it to pass the Travis build now.

@enzo1982

enzo1982 commented May 5, 2018

Copy link
Copy Markdown
Contributor Author

@erikd Any news on this? Are you going to merge it?

@erikd

erikd commented May 6, 2018

Copy link
Copy Markdown
Member

Sorry, forgot about this. Will look at it today. Please ping me again if this has not been merged within 24 hours.

Superceded by comment below.

@erikd

erikd commented May 6, 2018

Copy link
Copy Markdown
Member

I've just had a look at this and it looks good, but there is no test in the test suite that would fail if this was wrong.

Let my update the test suite on master (which will test the CRC functionality currently on master) then I can run the new tests with this code.

Update: I'm going to try and get these tests done over the next couple of days.

@enzo1982

enzo1982 commented May 7, 2018

Copy link
Copy Markdown
Contributor Author

Let me know if I can help with the tests. I could implement them and add the commits here.

@erikd

erikd commented May 8, 2018

Copy link
Copy Markdown
Member

Thanks for the offer, but this is one I'd prefer to do myself. This weekend at the latest.

@erikd

erikd commented May 13, 2018

Copy link
Copy Markdown
Member

And then life got in the way.

@enzo1982 If you could write some tests. Would be really good to do this in a separate PR, with just the tests (and removing the unused CRC8 functions). We could then get that merged and rebase this PR on top of it to make absolutely 100% sure nothing gets broken.

@enzo1982

Copy link
Copy Markdown
Contributor Author

OK, no problem. I think I can do this by Saturday.

@enzo1982

Copy link
Copy Markdown
Contributor Author

@erikd The test are ready now and I created PR #63. Please review.

@erikd

erikd commented May 20, 2018

Copy link
Copy Markdown
Member

Is this still needed? If so, it needs a rebase.

@enzo1982

Copy link
Copy Markdown
Contributor Author

Thanks for merging the tests! I'll rebase this one later today.

@enzo1982

Copy link
Copy Markdown
Contributor Author

The PR is rebased now. Should be ready for merging once the Travis build completes.

@erikd erikd merged commit 324c2fe into xiph:master May 20, 2018
@erikd

erikd commented May 20, 2018

Copy link
Copy Markdown
Member

Thanks @enzo1982 !

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants