Compute the Redwolf Checksum™ of some data

Question

I will preface this by saying that I made this for fun; I have absolutely no formal knowledge on cryptography or error correction. Do not use this algorithm in anything remotely important.

I was kind of bored a few days ago, so I decided to write a simple function to take some data and return an easily memorable (but not necessarily secure :p) checksum of it. The output format is a number of digits in base 36, between 0 and z (think of it like hexadecimal, but with all the letters used).

Your program or function will take two inputs: data, and block_size. The data will be a list of values 0 to 255, and the block_size will be at least 4. It will return a base 36 string (or list of values 0-36) with the length block_size.

Using [182, 109, 211, 144, 65, 109, 105, 135, 151, 233] and 4 as the inputs, this is how you would find the checksum:

1. The length of the data is padded with zeroes to a multiple of the block_size

   182, 109, 211, 144, 65, 109, 105, 135, 151, 233, 0, 0
   

2. The data is broken into blocks based on the block_size

   182  109  211  144
    65  109  105  135
   151  233    0    0
   

3. For each item n of the resulting block, take the sum of all items at position n in one of the above blocks mod 256

     182  109  211  144
   +  65  109  105  135
   + 151  233    0    0
   --------------------
     142  195   60   23
   

4. Take the binary representation of each item in the result

   10001110
   11000011
   00111100
   00010111
   

5. For each item, add the least significant five bits of the next (wrapping) item, and the least significant bit of the (wrapping) item after that (note that this value can be higher than 256)

      10001110   11000011   00111100   00010111
   +     00011      11100      10111      01110
   +         0          1          0          1
   --------------------------------------------
      10010001   11100000   01010011   00100110
   

6. Convert back to decimal, and take the mod 36

   1, 8, 11, 2
   

7. Covert into base 36

   18b2
   

A reference implementation can be found here. Input and output can be in any reasonable manner.

This is code-golf, so shortest in bytes per language wins!

Test cases

[]; 8                           -> 00000000
[0, 1, 2, 3, 4, 5, 6, 7]; 8     -> 14589cd8
[0, 1, 2, 3, 4, 5, 6, 7]; 6     -> eb589b
[0, 4, 2, 1]; 48                -> 473100000000000000000000000000000000000000000000
[195, 180, 1, 0]; 4             -> 0123
[31, 32, 65, 4]; 4              -> wxyz
[20, 8, 247, 41]; 4             -> tw4p
[250, 175, 225, 200]; 4         -> ewhb
[33]; 3                         -> (does not need to be handled)

Answer 1

K (ngn/k), 84 67 bytes

-17 bytes by reshuffling things, inspired by @Neil's comment.

{(,/($!10),`c$97+!26)36!+/256 32 2!'2(,/|0 1_)\+/-1_(0N;y)#x,0,y#0}

Try it online!

• +/-1_(0N;y)#x,0,y#0 take the column-wise sum of the input split into y-length chunks (filling with 0s)
• 2(,/|0 1_)\ build a list containing the original input, it rotated once, and it rotated twice (this uses the do overload of \ scan)
• 256 32 2!' mod the original input by 256, the rotated-once input by 32, and the rotated-twice input by 2
• 36!+/ sum column-wise, modding by 36
• (,/($!10),`c$97+!26) build list of base-36 characters (digits followed by lower case letters), which is indexed into by the results of the above

Answer 2

Thumb-2 (ARMv6T2, no div instructions), 118 116 112 110 bytes (ascii base 36)/102 bytes (values)

I believe there is still some optimization room for sure.

Raw machine code, 16-bit hex little endian

Base 36 ASCII version:

b5f0 ebad 0d03 466f 001d 2600 3d01 557e
d1fc b151 5dbc f810 5b01 192d 55bd 1c76
429e bf08 2600 3901 d1f4 003c 1e9d 7866
78a1 f000 f80c 3d01 d1f9 7866 7839 f000
f806 783e 7879 f000 f802 449d bdf0 f814
0b01 f006 061f 0849 4170 3824 dafd f110
01fb bfc8 3027 3054 f802 0b01 4770

Without ASCII conversion ('values')

b5f0 ebad 0d03 466f 001d 2600 3d01 557e
d1fc b151 5dbc f810 5b01 192d 55bd 1c76
429e bf08 2600 3901 d1f4 003c 1e9d 7866
78a1 f000 f80c 3d01 d1f9 7866 7839 f000
f806 783e 7879 f000 f802 449d bdf0 f814
0b01 f006 061f 0849 4170 3824 dafd 3024
f802 0b01 4770

Uncommented assembly:

        .syntax unified
        .arch armv6t2
        .thumb
        .globl redwolf
        .thumb_func
redwolf:
        push    {r4-r7,lr}
        sub.w   sp, sp, r3
        mov     r7, sp
        movs    r5, r3
        movs    r6, #0
.Lmemset_loop:
        subs    r5, #1
        strb    r6, [r7, r5]
        bne     .Lmemset_loop
.Lmemset_loop_end:
        cbz     r1, .Lsum_loop_end
.Lsum_loop:
        ldrb    r4, [r7, r6]
        ldrb.w  r5, [r0], #1
        adds    r5, r4
        strb    r5, [r7, r6]
        adds    r6, #1
        cmp     r6, r3
        it      eq
        moveq   r6, #0
        subs    r1, #1
        bne     .Lsum_loop
.Lsum_loop_end:
        movs    r4, r7
        subs    r5, r3, #2
.Lchecksum_loop:
        ldrb    r6, [r4, #1]
        ldrb    r1, [r4, #2]
        bl      checksum
        subs    r5, #1
        bhi     .Lchecksum_loop
.Lchecksum_loop_end:
        ldrb    r6, [r4, #1]
        ldrb    r1, [r7]
        bl      checksum
        ldrb    r6, [r7]
        ldrb    r1, [r7, #1]
        bl      checksum
        add     sp, r3
        pop     {r4-r7, pc}

        .thumb_func
checksum:
        ldrb.w  r0, [r4], #1
        and.w   r6, r6, #31
        lsrs    r1, r1, #1
        adcs    r0, r6
.Lmodulo_loop:
        subs    r0, #36
        bge     .Lmodulo_loop
.Lmodulo_loop_end:
#ifdef ASCII
        cmp.w   r0, #9 - 36
        it      gt
        addgt   r0, #'a'-10-'0'
        adds    r0, #'0'+36
#else
        adds    r0, #36
#endif
        strb.w  r0, [r2], #1
        bx      lr

Try it online! (sorta)

Explanation

C signature:

void redwolf(const uint8_t *data, size_t data_size, char *block, size_t block_size);

First, we push our registers and set up a VLA. (uint8_t chars[block_size])

        push    {r4-r7,lr}
        sub.w   sp, sp, r3

Since we like narrow instructions, and there is no narrow ldrb Rd, [Sp, Rn] instruction, we use a frame pointer to cut down code size.

        mov     r7, sp

Zero out the VLA we created.

        movs    r5, r3
        movs    r6, #0
.Lmemset_loop:
        subs    r5, #1
        strb    r6, [r7, r5]
        bne     .Lmemset_loop

If we have data, sum everything up.

.Lmemset_loop_end:
        cbz     r1, .Lsum_loop_end
.Lsum_loop:
        ldrb    r4, [r7, r6]
        ldrb.w  r5, [r0], #1
        adds    r5, r4
        strb    r5, [r7, r6]

r6 = (r6 + 1) % block_len without division

        adds    r6, #1
        cmp     r6, r3
        it      eq
        moveq   r6, #0

Decrement data_len and loop if non-zero.

        subs    r1, #1
        bne     .Lsum_loop

Now, we checksum the data and convert to base 36.

We do a simple loop for all but the last two bytes in chars, calling a subroutine (with a custom calling convention) to handle the arithmetic.

We pass the second two bytes as parameters, while checksum() will do *r4++ to load the first byte and increment.

.Lsum_loop_end:
        movs    r4, r7
        subs    r5, r3, #2
.Lchecksum_loop:
        ldrb    r6, [r4, #1]
        ldrb    r1, [r4, #2]
        bl      checksum
        subs    r5, #1
        bne     .Lchecksum_loop

Process the wrapped data. I feel this could be optimized better.

.Lchecksum_loop_end:
        ldrb    r6, [r4, #1]
        ldrb    r1, [r7]
        bl      checksum
        ldrb    r6, [r7]
        ldrb    r1, [r7, #1]
        bl      checksum

Restore the stack, pop registers, and return.

        add     sp, r3
        pop     {r4-r7, pc}

checksum subroutine

We call checksum with r6 = chars[i + 1] and r1 = chars[i + 2], with r2 still pointing to block.

Load chars[i] from r4 and increment the pointer. This is a step outlined from the other three calls.

        ldrb.w  r0, [r4], #1

Now we need to do chars[i] + (chars[i + 1] & 31) + (chars[i + 2] & 1).

First, we mask the lowest five bits of chars[i + 1].

        and.w   r6, r6, #31

Now, we use lsrs to get the lowest bit of chars[i + 2] in the carry flag...

        lsrs    r1, r1, #1

...so we can add them both with an add-with-carry. Done.

        adcs    r0, r6

Modulo by 36 using a naïve subtraction loop. No udiv required. Not that I would use it anyways - movs + udiv + mls would be 10 bytes, this is 4.

Note that this will end up negative, we need to add 36 after to get the correct result.

.Lmodulo_loop:
        subs    r0, #36
        bge     .Lmodulo_loop

Convert to base 36 (ascii version):

If r0 + 36 is > 9, we add the additional offset to get it from r0 + '0' to r0 + 'a' - 10.

.Lmodulo_loop_end:
        cmp.w   r0, #9 - 36
        it      gt
        addgt   r0, #'a'-10-'0'
        adds    r0, #'0' + 36

Adjust offset (non-ascii)

If we are outputting integers, just add 36.

        adds    r0, #36

Store the char into block and increment the pointer.

        strb.w  r0, [r2], #1

Return back to the main function.

        bx      lr

Answer 3

J, 59 bytes

(Num_j_,Alpha_j_){~]($!.0)36|[:+/256 32 2|i.@3|."{+/@([\~-)

Try it online!

• ([\~-) data x split in blocks of size y, padded with zeros
• +/@ sum each column
• i.@3|."{ rotate row by 0, 1 and 2, so we get 3 rows
• 256 32 2| mod rows by 256, 32 and 2
• [:+/ sum again
• 36| mod 36
• ]($!.0) lengthen list to size of y, padded with zeros
• (Num_j_,Alpha_j_){~ take the indices from 0…Z

Answer 4

05AB1E, 24 18 bytes

ιO₁%DÀ31&DÀÉ++₆%₆B

Try it online! or Try all cases!

Commented:

ι                    # create block_size lists of every block_size-th element
                     #   [data[0::block_size], data[1::block_size], ..., data[block_size-1::block_size]]
 O                   # sum each list
  ₁%                 # modulo 256
    DÀ               # duplicate the resulting list and rotate the copy left
      31&            # bitwise and 31 / take the 5 least significant bits
         DÀ          # duplicate this list and rotate left again
           É         # is the value odd? / least significant bit
            ++       # sum the three lists element-wise
              ₆%     # modulo 36
                ₆B   # convert to base 36

Answer 5

R, 122 bytes

function(d,b,m=matrix)c(0:9,letters)[1+colSums(m(rowSums(m(c(d,!1:(b-sum(d|1)%%b)),b))%%256,b+1,b)[1:3,]%%2^c(8,5,1))%%36]

Try it online!

Output as a list of base 36 digits (lowercase).

Answer 6

JavaScript (ES6),  122 121  114 bytes

Expects (data)(block_size). Returns an array of characters.

a=>w=>a.map((v,i)=>b[i%w]+=v,b=new Uint8Array(w))&&[...b].map((v,j)=>((v+b[++j%w]%32+b[-~j%w]%2)%36).toString(36))

Try it online!

Commented

Step 1 to step 3

a.map((v, i) =>         // for each value v at position i in a[]:
  b[i % w] += v,        //   add v to b[i mod w]
                        //   there's an implicit modulo 256 because ...
  b = new Uint8Array(w) //   ... b[] is initialized to an array of w unsigned bytes
)                       // end of map()

Step 4 to step 7

[...b]                  // we need to split b[] so that the results returned by the
                        // callback function of map() are not forced to unsigned bytes
.map((v, j) =>          // for each value v at position j in b[]:
  (                     //
    ( v +               //   compute the sum of v
      b[++j % w] % 32 + //   and b[(j + 1) mod w] mod 32
      b[-~j % w] % 2    //   and b[(j + 2) mod w] mod 2
    ) % 36              //   modulo 36
  ).toString(36)        //   converted to base-36
)                       // end of map()

Answer 7

Pip, 87 bytes

Y($+_)%256M(@>g<>@g)ZD0
((,tALz)Jx)@_M($+_)%36M Z[{@RVTBa}My{FB((TBa)@>-5)}M(@>y)AL@yy]

Try it online!

This was much harder than I expected.

Input is taken as a list of lines. First line is block_size, rest of the lines are the data.

Answer 8

Perl 5 -a, 96 bytes

$#r=<>-1;map$r[$i++%@r]+=$_,@F;say map{((0..9,a..z)x9)[$_%256+$r[++$j%@r]%32+$r[($j+1)%@r]%2]}@r

Try it online!

Answer 9

Python 3.8 (pre-release), 161 159 bytes

lambda d,b:(d:=d+[0]*(b-len(d)%b),r:=range(b),s:=[sum(d[i::b])%256for i in r],[[str(k:=(s[i]+(s[(i+1)%b]&31)+(s[(i+2)%b]&1))%36),chr(k+87)][k>9]for i in r])[2]

Try it online!

Edit:

• changed range to variable to reduce 2 characters

Answer 10

Ruby, 106 bytes

->a,n,c=[0]*n{a.size.times{|i|c[i%n]+=a[i]&255};(1..n).map{|i|((c[i-1]+c[i%n]%32+c[-~i%n]%2)%36).to_s 36}}

Try it online!

Answer 11

Charcoal, 29 bytes

⭆η⍘﹪ΣＥ851﹪↨Φθ¬﹪⁻⁻ξμιη¹Ｘ²Ｉλ³⁶φ

Try it online! Link is to verbose version of code. Explanation:

 η                              Block size
⭆                               Map over implicit range and join
      851                       Literal string `851`
     Ｅ                          Map over characters
            θ                   Data array
           Φ                   Filtered where 
                 ξ              Data index
                ⁻               Minus
                  μ             Character index
               ⁻                Minus
                   ι            Outer index
              ﹪                 Modulo
                    η           Block size
             ¬                  Leaves no remainder
          ↨          ¹          Convert from base 1
         ﹪                      Modulo
                       ²        Literal `2`
                      Ｘ         Raised to power
                         λ      Current character
                        Ｉ       Cast to integer
    Σ                           Take the sum
   ﹪                            Modulo
                          ³⁶    Literal 36
  ⍘                         φ   Convert to 0-z
                                Implicitly print

At one point conversion from base 1 is used to take the sum in case the list is empty (in which case the conversion is zero but the sum is None).

Answer 12

Pyth, 55 bytes

KeQJm%sd256.TchQKsm@+."/9ª!"G%++@Jd%@Jhd32%@Jhhd2 36K

Try it online!