001/*
002 * Logback: the reliable, generic, fast and flexible logging framework.
003 * Copyright (C) 1999-2026, QOS.ch. All rights reserved.
004 *
005 * This program and the accompanying materials are dual-licensed under
006 * either the terms of the Eclipse Public License v2.0 as published by
007 * the Eclipse Foundation
008 *
009 *   or (per the licensee's choosing)
010 *
011 * under the terms of the GNU Lesser General Public License version 2.1
012 * as published by the Free Software Foundation.
013 */
014package ch.qos.logback.core.kryo;
015
016/**
017 * CRC-3, polynomial {@code x^3 + x + 1} ({@code 0b1011}), init 0, MSB-first, no xorout.
018 *
019 * <p>Same remainder as a bit-at-a-time LFSR. Bytes use a 256-entry table plus an 8-entry
020 * “shift 8 zero bits” table so {@code crc(C, B) = ZERO8[C] xor TABLE[B]}.
021 */
022public final class Crc3 {
023
024    public static final int POLY = 0b1011;
025    public static final int MASK = 0b111;
026
027    /** Remainder of byte {@code i} starting from crc 0. */
028    private static final int[] TABLE = new int[256];
029
030    /** Remainder after 8 zero bits starting from crc {@code c}. */
031    private static final int[] ZERO8 = new int[8];
032
033    static {
034        for (int b = 0; b < 256; b++) {
035            TABLE[b] = crcByteSlow(0, b);
036        }
037        for (int c = 0; c < 8; c++) {
038            ZERO8[c] = crcByteSlow(c, 0);
039        }
040    }
041
042    private int crc;
043
044    static int crcByteSlow(int crc, int b) {
045        int c = crc & MASK;
046        for (int i = 7; i >= 0; i--) {
047            c = step(c, (b >>> i) & 1);
048        }
049        return c;
050    }
051
052    static int step(int crc, int bit) {
053        int mix = ((crc >>> 2) ^ (bit & 1)) & 1;
054        crc = (crc << 1) & MASK;
055        if (mix != 0) {
056            crc ^= 0b011;
057        }
058        return crc;
059    }
060
061    public void updateBit(int bit) {
062        crc = step(crc, bit);
063    }
064
065    /** {@code nbits} low bits of {@code value}, MSB first. */
066    public void updateBits(int value, int nbits) {
067        for (int i = nbits - 1; i >= 0; i--) {
068            updateBit((value >>> i) & 1);
069        }
070    }
071
072    public void update(int b) {
073        crc = tableByte(crc, b);
074    }
075
076    /** Remainder after one data byte from state {@code crc}. */
077    static int tableByte(int crc, int b) {
078        return ZERO8[crc & MASK] ^ TABLE[b & 0xFF];
079    }
080
081    public void update(byte[] data, int off, int len) {
082        int c = crc;
083        int end = off + len;
084        for (int i = off; i < end; i++) {
085            c = ZERO8[c] ^ TABLE[data[i] & 0xFF];
086        }
087        crc = c;
088    }
089
090    public int getValue() {
091        return crc & MASK;
092    }
093
094    public void reset() {
095        crc = 0;
096    }
097}