# Compute the Redwolf Checksum™ of some data

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 , 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)

• Can the base36 letters be uppercase?
– xash
Dec 17, 2020 at 16:13
• @xash Yes, the case doesn't matter at all Dec 17, 2020 at 16:14
• So in terms of binary operations that CPUs actually do, this is a SIMD sum of byte elements (with normal binary wrapping), similar to x86 paddb / _mm_add_epi8, reducing to 4 elements if you used a wider vector in the main loop. Then take that 4-byte "word" SIMD-byte-add two rotated and masked copies of it. (x + rotl(x, 8)&0x1f1f1f1f + rotl(x, 16)&0x01010101 where + is a SIMD byte add). It's very likely not a good checksum, but can run very fast on modern CPUs, just as fast as a simple sum of 4-byte integer elements. (Or faster for large unaligned buffers; group at the end.) Dec 18, 2020 at 19:14
• (One difference from how you described it is that you don't need to "convert" numbers to binary; integers in normal computers are already in binary. But it's not a bad thing to describe it that way, just overly complex for people used to languages with binary numbers.) Dec 18, 2020 at 19:38
• Oh I just realized that block_size=4 was only an example; it's not as easy as I thought to use CPU SIMD like MMX for the general case. In case anyone's interested, godbolt.org/z/rasY5P is a 3/4-finished x86 MMX implementation of that case, with main loop without odd-size handling, and the rotate/mask/add parts. Probably not viable as an answer because it doesn't easily extend to a variable block_size. Dec 18, 2020 at 20:18

# 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
• Having to specify the list of rotation amounts seems awkward, but not knowing K I don't know whether you're better off always rotating and then undoing one rotation later.
– Neil
Dec 17, 2020 at 20:00
• @Neil thanks! Managed to find a way to remove that redundancy, which also (somehow) removed the need for another round of 0-padding! Dec 17, 2020 at 20:56

## Thumb-2 (ARMv6T2, no div instructions), 118116112 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
strb    r5, [r7, r6]
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
pop     {r4-r7, pc}

.thumb_func
checksum:
ldrb.w  r0, [r4], #1
and.w   r6, r6, #31
lsrs    r1, r1, #1
.Lmodulo_loop:
subs    r0, #36
bge     .Lmodulo_loop
.Lmodulo_loop_end:
#ifdef ASCII
cmp.w   r0, #9 - 36
it      gt
#else
#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
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


        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


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


# 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

# 05AB1E, 24 18 bytes

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


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


# 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).

# 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()


# 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.

# 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!

# 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

# 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!

# 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).

# Pyth, 55 bytes

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


Try it online!