PRNG

{{
  "language": "Solidity",
  "sources": {
    "src/PRNG.sol": {
      "content": "// SPDX-License-Identifier: MIT
pragma solidity 0.8.28;

import "./common/CRC32.sol";
import {IPRNG} from "./common/interfaces/IPRNG.sol";

/// @title PRNG
/// @notice A contract that provides pseudo-random number generation based on signatures
/// @dev Inherits from CRC32 for hash calculation. Uses a combination of keccak256 and CRC32
/// to generate random numbers within a specified range
contract PRNG is CRC32, IPRNG {
    /// @notice Base points for percentage calculations (100.00%)
    uint256 public constant BASE_POINTS = 10000;

    /// @notice Maximum CRC32 hash value adjusted to prevent modulo bias
    /// @dev Calculated as the largest multiple of BASE_POINTS that fits in uint32
    uint32 public constant MAX_CRC32_HASH_VALUE =
        uint32(type(uint32).max - (type(uint32).max % BASE_POINTS));

    /// @notice Generates a pseudo-random number between 0 and BASE_POINTS
    /// @dev Uses signature as initial entropy, then applies keccak256 and CRC32
    /// repeatedly until a value below MAX_CRC32_HASH_VALUE is found to avoid modulo bias
    /// @param signature The input signature bytes to use as entropy source
    /// @return A pseudo-random number between 0 and BASE_POINTS (0-10000)
    function _rng(bytes calldata signature) internal view returns (uint32) {
        bytes32 hashVal = keccak256(signature);
        uint32 hashNum = crc32(hashVal);

        // Loop until we get a value below MAX_CRC32_HASH_VALUE (to avoid modulo bias)
        while (hashNum >= MAX_CRC32_HASH_VALUE) {
            hashVal = keccak256(abi.encodePacked(hashVal));
            hashNum = crc32(hashVal);
        }

        return uint32(hashNum % BASE_POINTS);
    }

    function rng(bytes calldata signature) public view returns (uint32) {
        return _rng(signature);
    }
}
"
    },
    "src/common/CRC32.sol": {
      "content": "// SPDX-License-Identifier: MIT
pragma solidity ^0.8.28;

/**
 * @title CRC32 Hash Calculator
 * @dev Implements the CRC-32 (Cyclic Redundancy Check) algorithm as defined by ISO-HDLC, IEEE 802.3, and others.
 *
 * ref: https://gist.github.com/kbhokray/683f4260f9c13a767fcfdac2ac3ee188
 * ref: https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-32-iso-hdlc
 *
 * check online:
 * https://www.browserling.com/tools/crc32-hash
 * https://crccalc.com/?crc=test&method=&datatype=ascii&outtype=hex
 *
 * The CRC-32 ISO-HDLC algorithm uses the following parameters:
 * - Width: 32 bits
 * - Polynomial: 0x04C11DB7 (expressed in the standard form used in specifications)
 * - Initial value: 0xFFFFFFFF
 * - Final XOR: 0xFFFFFFFF
 * - Reflect input: true (bits are processed LSB first)
 * - Reflect output: true (the final value is bit-reflected)
 *
 * Note on Polynomial Representation:
 * While the standard specification defines the polynomial as 0x04C11DB7, this implementation
 * uses 0x1DB710640. This discrepancy is due to implementation details in the table-based algorithm:
 *
 * 1. The standard polynomial (0x04C11DB7) gets bit-reflected to 0xEDB88320 for LSB-first processing
 * 2. For the table-driven implementation, we left-shift this reflected polynomial by 1 bit, resulting in 0x1DB710640
 *
 * This transformation is purely an optimization for the lookup table approach but produces
 * mathematically equivalent results to the standard algorithm.
 */
contract CRC32 {
    /**
     * @dev The CRC-32 polynomial used in the lookup table calculation.
     * This is NOT the canonical form (0x04C11DB7) from the spec, but rather:
     * - The bit-reflected value (0xEDB88320) left-shifted by 1 bit
     * - This transformation is required for the right-shift table-based implementation
     */
    uint256 private constant CRC_POLYNOMIAL = 0x1DB710640;

    /**
     * @dev Lookup table for fast CRC calculation.
     * Each entry represents the CRC value for a specific byte pattern.
     * These values are pre-computed based on CRC_POLYNOMIAL = 0x1DB710640
     */
    uint256[256] public crcTable = [
        0x00000000,
        0x77073096,
        0xEE0E612C,
        0x990951BA,
        0x076DC419,
        0x706AF48F,
        0xE963A535,
        0x9E6495A3,
        0x0EDB8832,
        0x79DCB8A4,
        0xE0D5E91E,
        0x97D2D988,
        0x09B64C2B,
        0x7EB17CBD,
        0xE7B82D07,
        0x90BF1D91,
        0x1DB71064,
        0x6AB020F2,
        0xF3B97148,
        0x84BE41DE,
        0x1ADAD47D,
        0x6DDDE4EB,
        0xF4D4B551,
        0x83D385C7,
        0x136C9856,
        0x646BA8C0,
        0xFD62F97A,
        0x8A65C9EC,
        0x14015C4F,
        0x63066CD9,
        0xFA0F3D63,
        0x8D080DF5,
        0x3B6E20C8,
        0x4C69105E,
        0xD56041E4,
        0xA2677172,
        0x3C03E4D1,
        0x4B04D447,
        0xD20D85FD,
        0xA50AB56B,
        0x35B5A8FA,
        0x42B2986C,
        0xDBBBC9D6,
        0xACBCF940,
        0x32D86CE3,
        0x45DF5C75,
        0xDCD60DCF,
        0xABD13D59,
        0x26D930AC,
        0x51DE003A,
        0xC8D75180,
        0xBFD06116,
        0x21B4F4B5,
        0x56B3C423,
        0xCFBA9599,
        0xB8BDA50F,
        0x2802B89E,
        0x5F058808,
        0xC60CD9B2,
        0xB10BE924,
        0x2F6F7C87,
        0x58684C11,
        0xC1611DAB,
        0xB6662D3D,
        0x76DC4190,
        0x01DB7106,
        0x98D220BC,
        0xEFD5102A,
        0x71B18589,
        0x06B6B51F,
        0x9FBFE4A5,
        0xE8B8D433,
        0x7807C9A2,
        0x0F00F934,
        0x9609A88E,
        0xE10E9818,
        0x7F6A0DBB,
        0x086D3D2D,
        0x91646C97,
        0xE6635C01,
        0x6B6B51F4,
        0x1C6C6162,
        0x856530D8,
        0xF262004E,
        0x6C0695ED,
        0x1B01A57B,
        0x8208F4C1,
        0xF50FC457,
        0x65B0D9C6,
        0x12B7E950,
        0x8BBEB8EA,
        0xFCB9887C,
        0x62DD1DDF,
        0x15DA2D49,
        0x8CD37CF3,
        0xFBD44C65,
        0x4DB26158,
        0x3AB551CE,
        0xA3BC0074,
        0xD4BB30E2,
        0x4ADFA541,
        0x3DD895D7,
        0xA4D1C46D,
        0xD3D6F4FB,
        0x4369E96A,
        0x346ED9FC,
        0xAD678846,
        0xDA60B8D0,
        0x44042D73,
        0x33031DE5,
        0xAA0A4C5F,
        0xDD0D7CC9,
        0x5005713C,
        0x270241AA,
        0xBE0B1010,
        0xC90C2086,
        0x5768B525,
        0x206F85B3,
        0xB966D409,
        0xCE61E49F,
        0x5EDEF90E,
        0x29D9C998,
        0xB0D09822,
        0xC7D7A8B4,
        0x59B33D17,
        0x2EB40D81,
        0xB7BD5C3B,
        0xC0BA6CAD,
        0xEDB88320,
        0x9ABFB3B6,
        0x03B6E20C,
        0x74B1D29A,
        0xEAD54739,
        0x9DD277AF,
        0x04DB2615,
        0x73DC1683,
        0xE3630B12,
        0x94643B84,
        0x0D6D6A3E,
        0x7A6A5AA8,
        0xE40ECF0B,
        0x9309FF9D,
        0x0A00AE27,
        0x7D079EB1,
        0xF00F9344,
        0x8708A3D2,
        0x1E01F268,
        0x6906C2FE,
        0xF762575D,
        0x806567CB,
        0x196C3671,
        0x6E6B06E7,
        0xFED41B76,
        0x89D32BE0,
        0x10DA7A5A,
        0x67DD4ACC,
        0xF9B9DF6F,
        0x8EBEEFF9,
        0x17B7BE43,
        0x60B08ED5,
        0xD6D6A3E8,
        0xA1D1937E,
        0x38D8C2C4,
        0x4FDFF252,
        0xD1BB67F1,
        0xA6BC5767,
        0x3FB506DD,
        0x48B2364B,
        0xD80D2BDA,
        0xAF0A1B4C,
        0x36034AF6,
        0x41047A60,
        0xDF60EFC3,
        0xA867DF55,
        0x316E8EEF,
        0x4669BE79,
        0xCB61B38C,
        0xBC66831A,
        0x256FD2A0,
        0x5268E236,
        0xCC0C7795,
        0xBB0B4703,
        0x220216B9,
        0x5505262F,
        0xC5BA3BBE,
        0xB2BD0B28,
        0x2BB45A92,
        0x5CB36A04,
        0xC2D7FFA7,
        0xB5D0CF31,
        0x2CD99E8B,
        0x5BDEAE1D,
        0x9B64C2B0,
        0xEC63F226,
        0x756AA39C,
        0x026D930A,
        0x9C0906A9,
        0xEB0E363F,
        0x72076785,
        0x05005713,
        0x95BF4A82,
        0xE2B87A14,
        0x7BB12BAE,
        0x0CB61B38,
        0x92D28E9B,
        0xE5D5BE0D,
        0x7CDCEFB7,
        0x0BDBDF21,
        0x86D3D2D4,
        0xF1D4E242,
        0x68DDB3F8,
        0x1FDA836E,
        0x81BE16CD,
        0xF6B9265B,
        0x6FB077E1,
        0x18B74777,
        0x88085AE6,
        0xFF0F6A70,
        0x66063BCA,
        0x11010B5C,
        0x8F659EFF,
        0xF862AE69,
        0x616BFFD3,
        0x166CCF45,
        0xA00AE278,
        0xD70DD2EE,
        0x4E048354,
        0x3903B3C2,
        0xA7672661,
        0xD06016F7,
        0x4969474D,
        0x3E6E77DB,
        0xAED16A4A,
        0xD9D65ADC,
        0x40DF0B66,
        0x37D83BF0,
        0xA9BCAE53,
        0xDEBB9EC5,
        0x47B2CF7F,
        0x30B5FFE9,
        0xBDBDF21C,
        0xCABAC28A,
        0x53B39330,
        0x24B4A3A6,
        0xBAD03605,
        0xCDD70693,
        0x54DE5729,
        0x23D967BF,
        0xB3667A2E,
        0xC4614AB8,
        0x5D681B02,
        0x2A6F2B94,
        0xB40BBE37,
        0xC30C8EA1,
        0x5A05DF1B,
        0x2D02EF8D
    ];

    /**
     * @dev Calculate CRC32 hash of a byte array.
     * This follows the ISO-HDLC standard for CRC-32 calculations.
     *
     * @param data The input byte array to calculate the CRC32 hash for
     * @return The 32-bit CRC value as a uint32
     */
    function crc32(bytes calldata data) public view returns (uint32) {
        unchecked {
            // Initialize CRC with all 1's (0xFFFFFFFF) as per the standard
            uint256 crc = 0xFFFFFFFF;

            // Process each byte in the input data
            for (uint256 i = 0; i < data.length; i++) {
                uint8 b = uint8(data[i]);

                // XOR the low byte of the current CRC with the input byte
                // Use this as an index into the lookup table
                // XOR the table value with the shifted CRC
                crc = (crc >> 8) ^ crcTable[(crc ^ uint256(b)) & 0xFF];
            }

            // Final XOR with all 1's (0xFFFFFFFF) as per the standard
            // and conversion to uint32 (which is the standard CRC-32 width)
            return uint32(crc ^ 0xFFFFFFFF);
        }
    }

    function crc32(bytes32 sigHash) public view returns (uint32) {
        unchecked {
            uint256 crc = 0xFFFFFFFF;

            // Process each byte in the bytes32 value directly
            for (uint256 i = 0; i < 32; i++) {
                // Extract byte at position i
                uint8 b = uint8(sigHash[i]);
                crc = (crc >> 8) ^ crcTable[(crc ^ uint256(b)) & 0xFF];
            }

            return uint32(crc ^ 0xFFFFFFFF);
        }
    }

    /**
     * @dev Calculate CRC32 hash of a string.
     * This is a convenience function that converts the string to bytes first.
     *
     * @param input The input string to calculate the CRC32 hash for
     * @return The 32-bit CRC value as a uint32
     */
    function crc32(string calldata input) public view returns (uint32) {
        return crc32(bytes(input));
    }
}
"
    },
    "src/common/interfaces/IPRNG.sol": {
      "content": "// SPDX-License-Identifier: MIT
pragma solidity 0.8.28;

/// @title IPRNG
/// @notice Interface for the PRNG contract that provides pseudo-random number generation
interface IPRNG {
    /// @notice Base points for percentage calculations (100.00%)
    function BASE_POINTS() external view returns (uint256);

    /// @notice Maximum CRC32 hash value adjusted to prevent modulo bias
    function MAX_CRC32_HASH_VALUE() external view returns (uint32);

    /// @notice Generates a pseudo-random number between 0 and BASE_POINTS
    /// @param signature The input signature bytes to use as entropy source
    /// @return A pseudo-random number between 0 and BASE_POINTS (0-10000)
    function rng(bytes calldata signature) external view returns (uint32);
}
"
    }
  },
  "settings": {
    "remappings": [
      "@openzeppelin/contracts/=lib/openzeppelin-contracts/contracts/",
      "@openzeppelin/contracts-upgradeable/=lib/openzeppelin-contracts-upgradeable/contracts/",
      "erc4626-tests/=lib/openzeppelin-contracts-upgradeable/lib/erc4626-tests/",
      "forge-std/=lib/forge-std/src/",
      "halmos-cheatcodes/=lib/openzeppelin-contracts-upgradeable/lib/halmos-cheatcodes/src/",
      "openzeppelin-contracts-upgradeable/=lib/openzeppelin-contracts-upgradeable/",
      "openzeppelin-contracts/=lib/openzeppelin-contracts/"
    ],
    "optimizer": {
      "enabled": true,
      "runs": 200
    },
    "metadata": {
      "useLiteralContent": false,
      "bytecodeHash": "ipfs",
      "appendCBOR": true
    },
    "outputSelection": {
      "*": {
        "*": [
          "evm.bytecode",
          "evm.deployedBytecode",
          "devdoc",
          "userdoc",
          "metadata",
          "abi"
        ]
      }
    },
    "evmVersion": "prague",
    "viaIR": true
  }
}}