Repository: netty/netty
Issue: Use CRC32-C in Snappy Framing Format Implementation

I have recently been researching Java Snappy implementations and came across a curiosity in netty's implementation.  Specifically, it looks like the code in:

https://github.com/netty/netty/blob/master/codec/src/main/java/io/netty/handler/codec/compression/Snappy.java

is using CRC32 rather than CRC32-C for its masked checksum computations.

The "Snappy framing format description" at:

https://code.google.com/p/snappy/source/browse/trunk/framing_format.txt

metions in section 3, "Checksum format", that:

"The checksums are always masked CRC-32Cs.  A description of CRC-32C can be found in RFC 3720, section 12.1, with examples in section B.4."

Other Java implementations I've come across take pains to use CRC-32C, typically defining the code themselves as in:

https://github.com/dain/snappy/blob/master/src/main/java/org/iq80/snappy/Crc32C.java

I didn't immediately find anything in the git history or the issues tracker that suggested this was an intentional choice, or if it might just be an oversight.  Please note it's not impacting me in any way, it's just something I came across and wanted to bring up in case it actually was an oversight.

Thanks,
Matt


Issue comments:
@nxmbriggs404 I don't think there is any "real" reason for this.... @lw346 could you have a look ?

Sure - I think it's just me failing to read the spec properly.  Will sort out by tomorrow.

This has been slightly hampered by the fact that java doesn't have unsigned types, but I think I've got this now.  I'm going to open a pull request as I'd like my bit-wrangling logic verifying.

@lw346 thanks for fixed.. cherry picked into 4.0 and master.


Pull request review comments:

Patch that resolved the issue:
diff --git a/codec/src/main/java/io/netty/handler/codec/compression/Crc32c.java b/codec/src/main/java/io/netty/handler/codec/compression/Crc32c.java
new file mode 100644
index 00000000000..b67c20004ae
--- /dev/null
+++ b/codec/src/main/java/io/netty/handler/codec/compression/Crc32c.java
@@ -0,0 +1,126 @@
+/*
+ * Copyright 2013 The Netty Project
+ *
+ * The Netty Project licenses this file to you under the Apache License,
+ * version 2.0 (the "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at:
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+package io.netty.handler.codec.compression;
+
+import java.util.zip.Checksum;
+
+/**
+ * Implements CRC32-C as defined in:
+ * "Optimization of Cyclic Redundancy-CHeck Codes with 24 and 32 Parity Bits",
+ * IEEE Transactions on Communications 41(6): 883-892 (1993).
+ *
+ * The implementation of this class has been sourced from the Appendix of RFC 3309,
+ * but with masking due to Java not being able to support unsigned types.
+ */
+class Crc32c implements Checksum {
+    private static final int[] CRC_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,
+    };
+
+    private static final int LONG_MASK = 0xFFFFFFFF;
+    private static final int BYTE_MASK = 0xFF;
+
+    private int crc = ~0;
+
+    @Override
+    public void update(int b) {
+        crc = crc32c(crc, b);
+    }
+
+    @Override
+    public void update(byte[] buffer, int offset, int length) {
+        for (int i = offset; i < offset + length; i++) {
+            crc = crc32c(crc, buffer[i]);
+        }
+    }
+
+    @Override
+    public long getValue() {
+        return (crc ^ LONG_MASK) & LONG_MASK;
+    }
+
+    @Override
+    public void reset() {
+        crc = ~0;
+    }
+
+    private static int crc32c(int crc, int b) {
+        return (crc >>> 8) ^ CRC_TABLE[(crc ^ (b & BYTE_MASK)) & BYTE_MASK];
+    }
+}
diff --git a/codec/src/main/java/io/netty/handler/codec/compression/Snappy.java b/codec/src/main/java/io/netty/handler/codec/compression/Snappy.java
index 3219f0b3ce5..c521c7bd3e5 100644
--- a/codec/src/main/java/io/netty/handler/codec/compression/Snappy.java
+++ b/codec/src/main/java/io/netty/handler/codec/compression/Snappy.java
@@ -18,8 +18,6 @@
 import io.netty.buffer.ByteBuf;
 import io.netty.buffer.ByteBufUtil;
 
-import java.util.zip.CRC32;
-
 /**
  * Uncompresses an input {@link ByteBuf} encoded with Snappy compression into an
  * output {@link ByteBuf}.
@@ -597,30 +595,30 @@ private static void validateOffset(int offset, int chunkSizeSoFar) {
     }
 
     /**
-     * Computes the CRC32 checksum of the supplied data and performs the "mask" operation
+     * Computes the CRC32C checksum of the supplied data and performs the "mask" operation
      * on the computed checksum
      *
-     * @param data The input data to calculate the CRC32 checksum of
+     * @param data The input data to calculate the CRC32C checksum of
      */
     public static int calculateChecksum(ByteBuf data) {
         return calculateChecksum(data, data.readerIndex(), data.readableBytes());
     }
 
     /**
-     * Computes the CRC32 checksum of the supplied data and performs the "mask" operation
+     * Computes the CRC32C checksum of the supplied data and performs the "mask" operation
      * on the computed checksum
      *
-     * @param data The input data to calculate the CRC32 checksum of
+     * @param data The input data to calculate the CRC32C checksum of
      */
     public static int calculateChecksum(ByteBuf data, int offset, int length) {
-        CRC32 crc32 = new CRC32();
+        Crc32c crc32 = new Crc32c();
         try {
             if (data.hasArray()) {
                 crc32.update(data.array(), data.arrayOffset() + offset, length);
             } else {
                 byte[] array = new byte[length];
                 data.getBytes(offset, array);
-                crc32.update(array);
+                crc32.update(array, 0, length);
             }
 
             return maskChecksum((int) crc32.getValue());
@@ -630,12 +628,12 @@ public static int calculateChecksum(ByteBuf data, int offset, int length) {
     }
 
     /**
-     * Computes the CRC32 checksum of the supplied data, performs the "mask" operation
+     * Computes the CRC32C checksum of the supplied data, performs the "mask" operation
      * on the computed checksum, and then compares the resulting masked checksum to the
      * supplied checksum.
      *
      * @param expectedChecksum The checksum decoded from the stream to compare against
-     * @param data The input data to calculate the CRC32 checksum of
+     * @param data The input data to calculate the CRC32C checksum of
      * @throws DecompressionException If the calculated and supplied checksums do not match
      */
     static void validateChecksum(int expectedChecksum, ByteBuf data) {
@@ -643,12 +641,12 @@ static void validateChecksum(int expectedChecksum, ByteBuf data) {
     }
 
     /**
-     * Computes the CRC32 checksum of the supplied data, performs the "mask" operation
+     * Computes the CRC32C checksum of the supplied data, performs the "mask" operation
      * on the computed checksum, and then compares the resulting masked checksum to the
      * supplied checksum.
      *
      * @param expectedChecksum The checksum decoded from the stream to compare against
-     * @param data The input data to calculate the CRC32 checksum of
+     * @param data The input data to calculate the CRC32C checksum of
      * @throws DecompressionException If the calculated and supplied checksums do not match
      */
     static void validateChecksum(int expectedChecksum, ByteBuf data, int offset, int length) {


Test patch:
diff --git a/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedDecoderTest.java b/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedDecoderTest.java
index 2b255443090..625ac1f1e05 100644
--- a/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedDecoderTest.java
+++ b/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedDecoderTest.java
@@ -147,10 +147,10 @@ public void testInvalidChecksumThrowsException() throws Exception {
     public void testInvalidChecksumDoesNotThrowException() throws Exception {
         EmbeddedChannel channel = new EmbeddedChannel(new SnappyFramedDecoder(true));
 
-        // checksum here is presented as -1568496083 (little endian)
+        // checksum here is presented as a282986f (little endian)
         ByteBuf in = Unpooled.wrappedBuffer(new byte[] {
            -0x80, 0x06, 0x00, 0x00, 0x73, 0x4e, 0x61, 0x50, 0x70, 0x59,
-            0x01, 0x09, 0x00, 0x00, 0x2d, -0x5a, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y'
+            0x01, 0x09, 0x00, 0x00, 0x6f, -0x68, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y'
         });
 
         channel.writeInbound(in);
diff --git a/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedEncoderTest.java b/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedEncoderTest.java
index 52edb9a67ba..3cc65ef5431 100644
--- a/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedEncoderTest.java
+++ b/codec/src/test/java/io/netty/handler/codec/compression/SnappyFramedEncoderTest.java
@@ -43,8 +43,9 @@ public void testSmallAmountOfDataIsUncompressed() throws Exception {
 
         ByteBuf expected = Unpooled.wrappedBuffer(new byte[] {
             -0x80, 0x06, 0x00, 0x00, 0x73, 0x4e, 0x61, 0x50, 0x70, 0x59,
-             0x01, 0x09, 0x00, 0x00, 0x2d, -0x5a, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y'
+             0x01, 0x09, 0x00, 0x00, 0x6f, -0x68, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y'
         });
+
         assertEquals(expected, channel.readOutbound());
     }
 
@@ -60,11 +61,12 @@ public void testLargeAmountOfDataIsCompressed() throws Exception {
 
         ByteBuf expected = Unpooled.wrappedBuffer(new byte[] {
             -0x80, 0x06, 0x00, 0x00, 0x73, 0x4e, 0x61, 0x50, 0x70, 0x59,
-             0x00, 0x0E, 0x00, 0x00, 0x7b, 0x1f, 0x65, 0x64,
+             0x00, 0x0E, 0x00, 0x00, 0x3b, 0x36, -0x7f, 0x37,
                    0x14, 0x10,
                    'n', 'e', 't', 't', 'y',
                    0x3a, 0x05, 0x00
         });
+
         assertEquals(expected, channel.readOutbound());
     }
 
@@ -81,8 +83,8 @@ public void testStreamStartIsOnlyWrittenOnce() throws Exception {
 
         ByteBuf expected = Unpooled.wrappedBuffer(new byte[] {
             -0x80, 0x06, 0x00, 0x00, 0x73, 0x4e, 0x61, 0x50, 0x70, 0x59,
-             0x01, 0x09, 0x00, 0x00, 0x2d, -0x5a, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y',
-             0x01, 0x09, 0x00, 0x00, 0x2d, -0x5a, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y',
+             0x01, 0x09, 0x00, 0x00, 0x6f, -0x68, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y',
+             0x01, 0x09, 0x00, 0x00, 0x6f, -0x68, -0x7e, -0x5e, 'n', 'e', 't', 't', 'y',
         });
 
         CompositeByteBuf actual = Unpooled.compositeBuffer();
diff --git a/codec/src/test/java/io/netty/handler/codec/compression/SnappyTest.java b/codec/src/test/java/io/netty/handler/codec/compression/SnappyTest.java
index c7122d1913d..0ac3d6574c9 100644
--- a/codec/src/test/java/io/netty/handler/codec/compression/SnappyTest.java
+++ b/codec/src/test/java/io/netty/handler/codec/compression/SnappyTest.java
@@ -175,7 +175,7 @@ public void testCalculateChecksum() {
         ByteBuf input = Unpooled.wrappedBuffer(new byte[] {
                 'n', 'e', 't', 't', 'y'
         });
-        assertEquals(maskChecksum(0xddaa8ce6), calculateChecksum(input));
+        assertEquals(maskChecksum(0xd6cb8b55), calculateChecksum(input));
     }
 
     @Test
@@ -184,7 +184,7 @@ public void testValidateChecksumMatches() {
                 'y', 't', 't', 'e', 'n'
         });
 
-        validateChecksum(maskChecksum(0x37c55159), input);
+        validateChecksum(maskChecksum(0x2d4d3535), input);
     }
 
     @Test(expected = DecompressionException.class)
@@ -193,6 +193,6 @@ public void testValidateChecksumFails() {
                 'y', 't', 't', 'e', 'n'
         });
 
-        validateChecksum(maskChecksum(0xddaa8ce6), input);
+        validateChecksum(maskChecksum(0xd6cb8b55), input);
     }
 }