Add methods to compute CRC checksums

[CsloudX]

I wish godot can't add crc build-in support, because it so common tool. I implemented it myself by GDScript, But I Still wish it can provide by build-in.

class_name XCRC

enum Type {
    CRC_CUSTOM,
    CRC8,CRC8_ITU,CRC8_ROHC,CRC8_MAXIM,
    CRC16, CRC16_MAXIM,CRC16_IBM, CRC16_USB,CRC16_MODBUS,CRC16_CCITT,CRC16_CCITT_FALSE,CRC16_X25,CRC16_XMODEM,CRC16_DNP,
    CRC32, CRC32_MPEG_2, #CRC32_B,CRC32_C,CRC32_D, CRC32_POSIX
}

var _map = {
    Type.CRC8:      {"width":8,"poly":0x07,"init_val":0x00,"x_or_out":0x00,"ref_in":false,"ref_out":false},
    Type.CRC8_ITU:  {"width":8,"poly":0x07,"init_val":0x00,"x_or_out":0x55,"ref_in":false,"ref_out":false},
    Type.CRC8_ROHC: {"width":8,"poly":0x07,"init_val":0xFF,"x_or_out":0x00,"ref_in":true,"ref_out":false},
    Type.CRC8_MAXIM:{"width":8,"poly":0x31,"init_val":0x00,"x_or_out":0x00,"ref_in":true,"ref_out":false},
#   CRC8_DARC:  return XCRC<uint8_t>(0x39, 0x00, 0x00, true, false);

    Type.CRC16:             {"width":16,"poly":0x1021,"init_val":0xFFFF,"x_or_out":0x0000,"ref_in":false,"ref_out":false},
    Type.CRC16_IBM:         {"width":16,"poly":0x8005,"init_val":0x0000,"x_or_out":0x0000,"ref_in":true,"ref_out":false},
    Type.CRC16_MAXIM:       {"width":16,"poly":0x8005,"init_val":0x0000,"x_or_out":0xFFFF,"ref_in":true,"ref_out":false},
    Type.CRC16_USB:         {"width":16,"poly":0x8005,"init_val":0xFFFF,"x_or_out":0xFFFF,"ref_in":true,"ref_out":false},
    Type.CRC16_MODBUS:      {"width":16,"poly":0x8005,"init_val":0xFFFF,"x_or_out":0x0000,"ref_in":true,"ref_out":false},
    Type.CRC16_CCITT:       {"width":16,"poly":0x1021,"init_val":0x0000,"x_or_out":0x0000,"ref_in":true,"ref_out":false},
    Type.CRC16_CCITT_FALSE: {"width":16,"poly":0x1021,"init_val":0xFFFF,"x_or_out":0x0000,"ref_in":false,"ref_out":false},
    Type.CRC16_X25:         {"width":16,"poly":0x1021,"init_val":0xFFFF,"x_or_out":0xFFFF,"ref_in":true,"ref_out":false},
    Type.CRC16_XMODEM:      {"width":16,"poly":0x1021,"init_val":0x0000,"x_or_out":0x0000,"ref_in":false,"ref_out":false},
    Type.CRC16_DNP:         {"width":16,"poly":0x3D65,"init_val":0x0000,"x_or_out":0xFFFF,"ref_in":true,"ref_out":false},
#   "CRC16/A", "CRC16", "1021", "C6C6", "0000", true, false,
#   "CRC16/DECT R", "CRC16", "0589", "0000", "0001", false, false,
#   "CRC16/DECT X", "CRC16", "0589", "0000", "0000", false, false,
#   "CRC16/GENIBUS", "CRC16", "1021", "FFFF", "FFFF", false, false,

    Type.CRC32:         {"width":32,"poly":0x04C11DB7,"init_val":0xFFFFFFFF,"x_or_out":0xFFFFFFFF,"ref_in":true,"ref_out":false},
    Type.CRC32_MPEG_2:  {"width":32,"poly":0x04C11DB7,"init_val":0xFFFFFFFF,"x_or_out":0x00000000,"ref_in":false,"ref_out":false},
#   "CRC32/B", "CRC32", "04C11DB7", "FFFFFFFF", "FFFFFFFF", false, false,
#   "CRC32/C", "CRC32", "1EDC6F41", "FFFFFFFF", "FFFFFFFF", true, false,
#   "CRC32/D", "CRC32", "A833982B", "FFFFFFFF", "FFFFFFFF", true, false,
#   "CRC32/POSIX", "CRC32", "04C11DB7", "00000000", "FFFFFFFF", false, false,
}

var type = Type.CRC8: set = set_type
var width = 8: set = set_width
var poly = 0x00: set = set_poly
var init_val = 0x00: set = set_init_val
var x_or_out = 0x00: set = set_x_or_out
var ref_in = false: set =  set_ref_in
var ref_out = false: set = set_ref_out

var _need_reset = false

var _table = []
var topbit = (0x01<<(width-1))
var _mask = 0xFF

func _init(_type = Type.CRC8):
    set_type(_type)

func maybe_reset():
    if _need_reset:
        reset()
        _need_reset = false

func reset():
    topbit = (0x01<<(width-1))
    match width:
        8:
            _mask = 0xFF
        16:
            _mask = 0xFFFF
        32:
            _mask = 0xFFFFFFFF
        _:
            assert(false)
    _create_table()

func calc(data:PackedByteArray):
    maybe_reset()
    var reg = init_val
    if ref_in:
        for c in data:
            var da = (reg&0x0F)
            reg = (reg>>4)&_mask
            reg = (reg^_table[da^(c&0x0F)])&_mask
            da = (reg&0x0F)
            reg = (reg>>4)&_mask
            reg = (reg^_table[da^(c>>4)])&_mask
#           XGlobal.print(reg)
    else:
        var shift = width-4 # width-8+4
        for c in data:
            var da = (reg>>shift)&_mask
            reg <<= 4
            reg = (reg^_table[(da^(c>>4))&_mask])&_mask
            da = (reg>>shift)&_mask
            reg <<= 4
            reg = (reg^_table[da^(c&0x0F)])&_mask

    if ref_out:
        return _reflected(reg)^x_or_out
    else:
        return reg^x_or_out

func _reflected(_poly):
    var ret = 0
    for i in width:
        if ((0x01<<i)&_poly):
            ret |= (0x01<<(width-i-1))
    return ret

func _create_table():
    _table.resize(16)
    if ref_in:
        var use_poly = _reflected(poly)
        for i in 16:
            var reg = i
            for bit in 4:
                if (reg&0x01):
                    reg = (reg>>1)^use_poly
                else:
                    reg = (reg>>1)
            _table[i] = reg
    else:
        for i in 16:
            var reg = i
            for bit in width:
                if (reg&topbit):
                    reg = (reg<<1)^poly
                else:
                    reg = (reg<<1)
            _table[i] = reg&_mask

func set_type(_type):
    type = _type
    if type==Type.CRC_CUSTOM:
        return

    assert(_map.has(type))
    var data = _map[type]
    width = data["width"]
    poly = data["poly"]
    init_val = data["init_val"]
    x_or_out = data["x_or_out"]
    ref_in = data["ref_in"]
    ref_out = data["ref_out"]
    reset()
    _need_reset = false

func set_width(value:int):
    assert(value%8==0)
    width = value
    _need_reset = true

func set_poly(value:int):
    poly = value
    _need_reset = true

func set_init_val(value:int):
    init_val = value
    _need_reset = true

func set_x_or_out(value:int):
    x_or_out = value
    _need_reset = true

func set_ref_in(value:bool):
    ref_in = value
    _need_reset = true

func set_ref_out(value:bool):
    ref_out = value
    _need_reset = true

I Love Godot So Much!

[YuriSizov]

You have to follow the proposal template and answer the questions provided for it to be considered. One of the important points to explain would be the reason for inclusion into core when you can clearly make it a plugin.

[Xrayez]

Thanks for sharing the snippets, but I'm curious what do you need these methods for? Godot does provide MD5/SHA functions, so I think it makes sense to have CRC implemented as well?

In any case, you are free to create an addon and share it on the AssetLib.

If you didn't know, we have a place to share plugin/addon/modules ideas at https://github.com/godot-extended-libraries/godot-ideas as well.

If performance is concern, then maybe these methods are worth implementing via GDNative or C++ modules approach. I'm maintaining Goost extension which aims to fulfill those needs, but then again there have to be at least some real-life use cases to justify implementing those methods anyways (specifically in the gamedev field, because CRC is surely more useful in other fields).

Keep in mind that Godot aims to be small.

[Calinou]

See also https://github.com/godotengine/godot-proposals/issues/1386.

[CsloudX]

I think engine is a powerful tools, and CRC is a common tool. CRC doesn't cause godot engine become bigger obvioursly. In my case, I can use CRC calculate OS.get_unique_id() to a sortly unique_id(), it cool. MD5/SHA doesn't meet my needs. I just wish can builtin. Sorry my english not good, I love Godot

[Calinou]

MD5/SHA doesn't meet my needs.

Could you explain why it doesn't meet your needs?

CRC has many known vulnerabilities and is not recommended for anything that requires security. If performance is your concern (and MD5 is actually too slow for your needs), consider looking into xxHash (see https://github.com/godotengine/godot-proposals/issues/1386).

[CsloudX]

I can use CRC calculate OS.get_unique_id() to a sortly unique_id()

	id	short_id
MD5	52479854556874254	811AF586FCD417D9
SHA1	52479854556874254	aed2cab49ac3a66d563fdc0aaef38f0c16c04f26
CRC16	52479854556874254	F674

I wish covert my machine_id (very long) to a shortly id (maybe I can remeber it so easy, or need my friend tell me the id) and I think CRC is a basic tool.

[Calinou]

Closing due to lack of support. (Also, the proposal still doesn't follow the template.)

If having a short ID is your goal, you can compute a MD5 checksum and store it in a differently encoded string (e.g. Base64), or only store the first 4-8 characters. Doing the latter will increase the risk of collisions though.