TheNullicorn · March 5, 2022 21:55
diff --git a/0_README.md b/0_README.md
diff --git a/1_simple.kts b/1_simple.kts
 // A constant used as the divisor in CRC arithmetic.
 val polynomial = 0b10011

 // The index of the highest 1 bit in the polynomial, aka its "width".
 val width = Int.SIZE_BITS - polynomial.countLeadingZeroBits() - 1

 // A bitmask over the most significant bit in the divisionBuffer. The masked bit is the one at
 // (width - 1).
 val divisionCheckMask = 1 shl (width - 1)

 // A bitmask over all bits in the divisionBuffer. The highest masked bit is at the index equal to
 // width.
 val bufferMask = (1 shl width) - 1

 /**
 * A Kotlin implementation of Ross N. Williams' "SIMPLE" CRC algorithm.
 *
 * Based on Section 8 of his paper, "A Painless Guide to CRC Error Detection Algorithms".
 * Original  ——> http://ross.net/crc/download/crc_v3.txt
 * Archive   ——> https://redirect.nullicorn.me/docs/ross_crc_formatted
 *  - Hosted on Google Docs
 *  - Contains an outline for easier navigation
 */
 fun Int.simpleCrc(): Int {
    // Only the lowest `w` bits of this value matter, where `w = width`.
    // This field stores the remainder as it evolves throughout the long division.
    var divisionBuffer = 0

    // Long division (32-bit, base 2, no carries).
    // Instead of shifting the value itself left by `width` (and using `downTo 0`), we just pretend
    // those zeros are there by going `downTo -width + 1`, and assuming any bits where `i < 0` are
    // 0.
    for (i in Int.SIZE_BITS downTo -width + 1) {
        // Only divide (XOR) on this iteration if the highest bit in the buffer is in the same
        // position as the one in the polynomial. Otherwise, continue to accumulate bits in the
        // buffer.
        val canDivide = (divisionBuffer and divisionCheckMask) != 0

        // "Bring down" the next digit (0 or 1) from the original message and put it in the buffer's
        // least-significant position, shifting everything else to the left once.
        divisionBuffer = divisionBuffer
            .shl(1)
            .or(if (i >= 0) this ushr (i - 1) and 1 else 0)

        // Divide (XOR) on this iteration if we determined earlier that we would.
        if (canDivide) divisionBuffer = divisionBuffer xor polynomial
    }

    // Only return the least-significant bits of the buffer, which represent the remainder of the
    // division. Any other bits in the buffer are leftover bits that have already been shifted out
    // of the relevant section.
    return divisionBuffer and bufferMask
 }

 val samples = arrayOf(
    0b1101011011,                      // CRC = 1110 = 14
    0b01101110001100100101000101001101 // CRC = 0110 = 6
 )

 for (message in samples) {
    println("$message ——> ${message.simpleCrc()}")
 }

 // Verified using this calculator: https://asecuritysite.com/comms/crc_div
 // (as well as Ross's paper itself)
diff --git a/2_table_reverse.kts b/2_table_reverse.kts
 /**
 * A Kotlin implementation of the reversed/reflected table-driven CRC algorithm.
 *
 * @param[polynomial] The divisor used when dividing.
 * @param[width] The number of bits to use when generating the [output].
 * @param[isReversed] Whether the inputs and outputs of the calculator should reverse the order of
 * the least-significant bits.
 * @param[initialValue] The value used to initialize the calculator's registry.
 * @param[outputXor] The value that the [output] should be [XOR][Int.xor]ed by before being
 * returned.
 */
 class CrcCalculator(
    polynomial: Int,
    private val width: Int,
    private val isReversed: Boolean,
    private val initialValue: Int,
    private val outputXor: Int,
 ) {
    private var divBuffer = initialValue

    /**
     * A bitmask over only the bit whose position is [width] `- 1` from the right side (least
     * significant).
     *
     * For example, if `width = 5`, this would be equal to `0b100000`.
     */
    private val topBitMask = 1 shl (width - 1)

    /**
     * A bitmask over every bit whose position is lower than [width], starting from the right side
     * (least significant).
     *
     * For example, if `width = 5`, this would be equal to `0b011111`.
     */
    private val lowBitsMask = ((1L shl width) - 1).toInt()

    private val xorTable = IntArray(256) { index ->
        // Use the index itself as the initial buffer value; reversed if necessary.
        val byte = if (isReversed) {
            index.reversed(width = 8)
        } else {
            index
        }
        // Shift the initial value into the leftmost byte of the buffer.
        var divByteBuffer = byte shl (width - 8)

        // Perform polynomial division.
        for (b in 0 until 8) divByteBuffer =
            if (divByteBuffer and topBitMask == 0) divByteBuffer shl 1
            else divByteBuffer shl 1 xor polynomial

        // Reverse the output if necessary.
        if (isReversed)
            divByteBuffer = divByteBuffer.reversed(width)
        return@IntArray divByteBuffer and lowBitsMask
    }

    /**
     * The CRC value calculated for all data provided to the calculator.
     *
     * Only data passed to the update functions since the last [reset] is included in the
     * calculation. If that calculator hasn't been reset, all data is used.
     */
    val output: Int
        get() = divBuffer xor outputXor

    /**
     * Reverts the calculator to its initial state, as if [updateOnce] had never been called.
     *
     * This allows the same calculator to be reused for multiple distinct CRCs.
     */
    fun reset() {
        divBuffer = initialValue
    }

    /**
     * Updates the calculation using the `8` least-significant bits of the supplied [message].
     */
    fun updateOnce(message: Int) {
        if (isReversed)
            divBuffer = xorTable[divBuffer xor message and 0xFF] xor (divBuffer ushr 8)
        else
            divBuffer = xorTable[divBuffer ushr 24 xor message and 0xFF] xor (divBuffer shl 8)
    }

    /**
     * Updates the calculation once for each byte in the supplied [message], in order.
     */
    fun updateMany(message: ByteArray) {
        for (byte in message)
            updateOnce(byte.toInt())
    }

    /**
     * Updates the calculation once for each character in the supplied [message], in order.
     */
    fun updateString(message: String) {
        for (char in message)
            updateOnce(char.code)
    }
 }

 /**
 * From [here](https://gist.github.com/TheNullicorn/41f9a56ad084ee8aac8f2138507b162b).
 */
 fun Int.reversed(width: Int = Int.SIZE_BITS): Int {
    var reverse = this

    for (i in 0 until width) {
        // The value of the non-reflected bit.
        val sourceBit = this shr i and 1
        // A mask with only the bit in the reflected position set.
        val targetBit = 1 shl (width - i - 1)

        // Set or clear the target bit depending on the source bit's current state.
        reverse = if (sourceBit != 0)
            reverse or targetBit
        else
            reverse and targetBit.inv()
    }

    return reverse
 }
	// A constant used as the divisor in CRC arithmetic.
	val polynomial = 0b10011

	// The index of the highest 1 bit in the polynomial, aka its "width".
	val width = Int.SIZE_BITS - polynomial.countLeadingZeroBits() - 1

	// A bitmask over the most significant bit in the divisionBuffer. The masked bit is the one at
	// (width - 1).
	val divisionCheckMask = 1 shl (width - 1)

	// A bitmask over all bits in the divisionBuffer. The highest masked bit is at the index equal to
	// width.
	val bufferMask = (1 shl width) - 1

	/**
	* A Kotlin implementation of Ross N. Williams' "SIMPLE" CRC algorithm.
	*
	* Based on Section 8 of his paper, "A Painless Guide to CRC Error Detection Algorithms".
	* Original ——> http://ross.net/crc/download/crc_v3.txt
	* Archive ——> https://redirect.nullicorn.me/docs/ross_crc_formatted
	* - Hosted on Google Docs
	* - Contains an outline for easier navigation
	*/
	fun Int.simpleCrc(): Int {
	// Only the lowest `w` bits of this value matter, where `w = width`.
	// This field stores the remainder as it evolves throughout the long division.
	var divisionBuffer = 0

	// Long division (32-bit, base 2, no carries).
	// Instead of shifting the value itself left by `width` (and using `downTo 0`), we just pretend
	// those zeros are there by going `downTo -width + 1`, and assuming any bits where `i < 0` are
	// 0.
	for (i in Int.SIZE_BITS downTo -width + 1) {
	// Only divide (XOR) on this iteration if the highest bit in the buffer is in the same
	// position as the one in the polynomial. Otherwise, continue to accumulate bits in the
	// buffer.
	val canDivide = (divisionBuffer and divisionCheckMask) != 0

	// "Bring down" the next digit (0 or 1) from the original message and put it in the buffer's
	// least-significant position, shifting everything else to the left once.
	divisionBuffer = divisionBuffer
	.shl(1)
	.or(if (i >= 0) this ushr (i - 1) and 1 else 0)

	// Divide (XOR) on this iteration if we determined earlier that we would.
	if (canDivide) divisionBuffer = divisionBuffer xor polynomial
	}

	// Only return the least-significant bits of the buffer, which represent the remainder of the
	// division. Any other bits in the buffer are leftover bits that have already been shifted out
	// of the relevant section.
	return divisionBuffer and bufferMask
	}

	val samples = arrayOf(
	0b1101011011, // CRC = 1110 = 14
	0b01101110001100100101000101001101 // CRC = 0110 = 6
	)

	for (message in samples) {
	println("$message ——> ${message.simpleCrc()}")
	}

	// Verified using this calculator: https://asecuritysite.com/comms/crc_div
	// (as well as Ross's paper itself)
	/**
	* A Kotlin implementation of the reversed/reflected table-driven CRC algorithm.
	*
	* @param[polynomial] The divisor used when dividing.
	* @param[width] The number of bits to use when generating the [output].
	* @param[isReversed] Whether the inputs and outputs of the calculator should reverse the order of
	* the least-significant bits.
	* @param[initialValue] The value used to initialize the calculator's registry.
	* @param[outputXor] The value that the [output] should be [XOR][Int.xor]ed by before being
	* returned.
	*/
	class CrcCalculator(
	polynomial: Int,
	private val width: Int,
	private val isReversed: Boolean,
	private val initialValue: Int,
	private val outputXor: Int,
	) {
	private var divBuffer = initialValue

	/**
	* A bitmask over only the bit whose position is [width] `- 1` from the right side (least
	* significant).
	*
	* For example, if `width = 5`, this would be equal to `0b100000`.
	*/
	private val topBitMask = 1 shl (width - 1)

	/**
	* A bitmask over every bit whose position is lower than [width], starting from the right side
	* (least significant).
	*
	* For example, if `width = 5`, this would be equal to `0b011111`.
	*/
	private val lowBitsMask = ((1L shl width) - 1).toInt()

	private val xorTable = IntArray(256) { index ->
	// Use the index itself as the initial buffer value; reversed if necessary.
	val byte = if (isReversed) {
	index.reversed(width = 8)
	} else {
	index
	}
	// Shift the initial value into the leftmost byte of the buffer.
	var divByteBuffer = byte shl (width - 8)

	// Perform polynomial division.
	for (b in 0 until 8) divByteBuffer =
	if (divByteBuffer and topBitMask == 0) divByteBuffer shl 1
	else divByteBuffer shl 1 xor polynomial

	// Reverse the output if necessary.
	if (isReversed)
	divByteBuffer = divByteBuffer.reversed(width)
	return@IntArray divByteBuffer and lowBitsMask
	}

	/**
	* The CRC value calculated for all data provided to the calculator.
	*
	* Only data passed to the update functions since the last [reset] is included in the
	* calculation. If that calculator hasn't been reset, all data is used.
	*/
	val output: Int
	get() = divBuffer xor outputXor

	/**
	* Reverts the calculator to its initial state, as if [updateOnce] had never been called.
	*
	* This allows the same calculator to be reused for multiple distinct CRCs.
	*/
	fun reset() {
	divBuffer = initialValue
	}

	/**
	* Updates the calculation using the `8` least-significant bits of the supplied [message].
	*/
	fun updateOnce(message: Int) {
	if (isReversed)
	divBuffer = xorTable[divBuffer xor message and 0xFF] xor (divBuffer ushr 8)
	else
	divBuffer = xorTable[divBuffer ushr 24 xor message and 0xFF] xor (divBuffer shl 8)
	}

	/**
	* Updates the calculation once for each byte in the supplied [message], in order.
	*/
	fun updateMany(message: ByteArray) {
	for (byte in message)
	updateOnce(byte.toInt())
	}

	/**
	* Updates the calculation once for each character in the supplied [message], in order.
	*/
	fun updateString(message: String) {
	for (char in message)
	updateOnce(char.code)
	}
	}

	/**
	* From [here](https://gist.github.com/TheNullicorn/41f9a56ad084ee8aac8f2138507b162b).
	*/
	fun Int.reversed(width: Int = Int.SIZE_BITS): Int {
	var reverse = this

	for (i in 0 until width) {
	// The value of the non-reflected bit.
	val sourceBit = this shr i and 1
	// A mask with only the bit in the reflected position set.
	val targetBit = 1 shl (width - i - 1)

	// Set or clear the target bit depending on the source bit's current state.
	reverse = if (sourceBit != 0)
	reverse or targetBit
	else
	reverse and targetBit.inv()
	}

	return reverse
	}