RDB file: CRC64 checksum

Challenges
1

My question is not a requirement of any challenge, but just curiosity.

How the crc64 in rdb file provided in “RDB Persistence” section are computed by testers?

This is the example in hex string (ignore spaces) I got from a CodeCrafter test case in stage “Read a key” #jz6:

52 45 44 49 53
30 30 31 31

fa
09 72 65 64 69 73 2d 76 65 72
05 37 2e 32 2e 30

fa
0a 72 65 64 69 73 2d 62 69 74 73
c0 40

fe
00
fb
01
00

00
06 62 61 6e 61 6e 61
0a 73 74 72 61 77 62 65 72 72 79

ff
ea d6 77 96 0d d5 e3 65

The value “ea d6 77 96 0d d5 e3 65” is 7341946071879767786 (little-endian) or 16921844136252138341 (big-endian).

I tried different poly values:

I tried both cases:

  • exclue “ff ea d6 77 96 0d d5 e3 65”
  • include “ff ea d6 77 96 0d d5 e3 65”

But cannot result in either crc64 7341946071879767786 (little-endian) or 16921844136252138341 (big-endian) in the given example.

So, could anyone tell me

  • What is the poly value to be used by testers?
  • Which content in the example above should be included in the crc64 computation?
  • Is there anything I am missing in the calculation? For example, in this tool, I see that there are some more input fields rather than just the poly value.
  • It would be nice if you could use an online tool and give me the screenshot of the tool with the input/output.

Thank you a lot!

2

Thanks for your questions! I’ll check with the team and get back to you as soon as I can.

1 Like
4

I found a partial answer. Below is explained in Go.

First of all, the poly should be bitwise-reversed of 0xad93d23594c935a9

bits.Reverse64(0xad93d23594c935a9) // 0x95ac9329ac4bc9b5

Secondly, the Go package hash/crc64 DO REVERSE the current crc value when computing new crc, then DO REVERSE the new crc again. This logic is fixed in hash/crc64.

The tester using github.com/hdt3213/rdb v1.0.18. This package DO NOT REVERSE crc value at all.

Below is the code diff from both packages.

// code from hash/crc64
func update(crc uint64, tab *Table, p []byte) uint64 {
    buildSlicing8TablesOnce()
    crc = ^crc

    // exclude same logic

    return ^crc
}

// code from github.com/hdt3213/rdb
func update(crc uint64, tab *Table, p []byte) uint64 {
    buildSlicing8TablesOnce()

    // exclude same logic

    return crc
}

I copied the code from hdt3213/rdb and tried to add the missing logic from hash/crc64. This produces the consistent result between 2 packages.

However, I cannot produce the crc in the example yet even with hdt3213/rdb and the correct poly. I will come back if I find something.

1 Like
5

Coud you please check this code and tell me what’s wrong Go Playground - The Go Programming Language

6

OK. I found the correct computation.
We need to include the EOF opcode 0xFF.

package main

import (
	"encoding/binary"
	"encoding/hex"
	"fmt"
	"strings"

	"github.com/hdt3213/rdb/crc64jones"
	"github.com/rs/zerolog/log"
)

func main() {
	data := []byte("123456789")
	crc := crc64jones.New()
	crc.Write(data)
	crcHex := fmt.Sprintf("%016x", crc.Sum64())
	fmt.Println(crcHex)
	if crcHex != "e9c6d914c4b8d9ca" {
		log.Error().Msg("CRC mismatch")
	}

	data = hexToBytes(
		`52 45 44 49 53 30 30 31 31 fa 09 72 65 64 69 73 2d 76 65 72 05 37 2e 32 2e 30 fa 0a 72 65 64 69 73 2d 62 69 74 73 c0 40 fe 00 fb 01 00 00 06 6f 72 61 6e 67 65 09 62 6c 75 65 62 65 72 72 79 ff`,
		// 35 42 87 36 10 d3 17 f6
	)
	crc = crc64jones.New()
	crc.Write(data)
	fmt.Printf("%016x\n", binary.BigEndian.Uint64(crc.Sum(nil)))

	data = hexToBytes(
		`52 45 44 49 53 30 30 31 31 fa 09 72 65 64 69 73 2d 76 65 72 05 37 2e 32 2e 30 fa 0a 72 65 64 69 73 2d 62 69 74 73 c0 40 fe 00 fb 01 00 00 06 62 61 6e 61 6e 61 0a 73 74 72 61 77 62 65 72 72 79 ff`,
		// ea d6 77 96 0d d5 e3 65
	)
	crc = crc64jones.New()
	crc.Write(data)
	fmt.Printf("%016x\n", binary.BigEndian.Uint64(crc.Sum(nil)))
}

func hexToBytes(h string) []byte {
	h = strings.ReplaceAll(h, " ", "")
	data, _ := hex.DecodeString(h)
	return data
}
1 Like
8

This topic was automatically closed 5 days after the last reply. New replies are no longer allowed.