View Javadoc
1   /*
2    * Logback: the reliable, generic, fast and flexible logging framework.
3    * Copyright (C) 1999-2026, QOS.ch. All rights reserved.
4    *
5    * This program and the accompanying materials are dual-licensed under
6    * either the terms of the Eclipse Public License v2.0 as published by
7    * the Eclipse Foundation
8    *
9    *   or (per the licensee's choosing)
10   *
11   * under the terms of the GNU Lesser General Public License version 2.1
12   * as published by the Free Software Foundation.
13   */
14  package ch.qos.logback.core.kryo;
15  
16  /**
17   * CRC-3, polynomial {@code x^3 + x + 1} ({@code 0b1011}), init 0, MSB-first, no xorout.
18   *
19   * <p>Same remainder as a bit-at-a-time LFSR. Bytes use a 256-entry table plus an 8-entry
20   * “shift 8 zero bits” table so {@code crc(C, B) = ZERO8[C] xor TABLE[B]}.
21   */
22  public final class Crc3 {
23  
24      public static final int POLY = 0b1011;
25      public static final int MASK = 0b111;
26  
27      /** Remainder of byte {@code i} starting from crc 0. */
28      private static final int[] TABLE = new int[256];
29  
30      /** Remainder after 8 zero bits starting from crc {@code c}. */
31      private static final int[] ZERO8 = new int[8];
32  
33      static {
34          for (int b = 0; b < 256; b++) {
35              TABLE[b] = crcByteSlow(0, b);
36          }
37          for (int c = 0; c < 8; c++) {
38              ZERO8[c] = crcByteSlow(c, 0);
39          }
40      }
41  
42      private int crc;
43  
44      static int crcByteSlow(int crc, int b) {
45          int c = crc & MASK;
46          for (int i = 7; i >= 0; i--) {
47              c = step(c, (b >>> i) & 1);
48          }
49          return c;
50      }
51  
52      static int step(int crc, int bit) {
53          int mix = ((crc >>> 2) ^ (bit & 1)) & 1;
54          crc = (crc << 1) & MASK;
55          if (mix != 0) {
56              crc ^= 0b011;
57          }
58          return crc;
59      }
60  
61      public void updateBit(int bit) {
62          crc = step(crc, bit);
63      }
64  
65      /** {@code nbits} low bits of {@code value}, MSB first. */
66      public void updateBits(int value, int nbits) {
67          for (int i = nbits - 1; i >= 0; i--) {
68              updateBit((value >>> i) & 1);
69          }
70      }
71  
72      public void update(int b) {
73          crc = tableByte(crc, b);
74      }
75  
76      /** Remainder after one data byte from state {@code crc}. */
77      static int tableByte(int crc, int b) {
78          return ZERO8[crc & MASK] ^ TABLE[b & 0xFF];
79      }
80  
81      public void update(byte[] data, int off, int len) {
82          int c = crc;
83          int end = off + len;
84          for (int i = off; i < end; i++) {
85              c = ZERO8[c] ^ TABLE[data[i] & 0xFF];
86          }
87          crc = c;
88      }
89  
90      public int getValue() {
91          return crc & MASK;
92      }
93  
94      public void reset() {
95          crc = 0;
96      }
97  }