// Dual-sum checksum examples -- Chapter 6

// Copyright 2024 Philip Koopman
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//    http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "chapter6_examples.h"

static const uint32_t initialSeed = SEED;  // Initial sum

// ----------------------
// Example from section 6.6.1  
// Baseline dual-sum checksum
// dataWord: data word in 8-bit blocks
// dwSize:   number of blocks in the data word
// modulus:  modulus for both running sums

uint32_t DualSum16_A(uint8_t dataWord[],
                     uint32_t dwSize, uint32_t modulus) 
{ 
  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all bytes in data word
  for(uint32_t index = 0; index < dwSize; index++)
  { 
    // Add next data word byte with modulus
    sumA = (sumA + (uint32_t)dataWord[index])% modulus;
    sumB = (sumB + sumA)% modulus;
  }

  // Shift sumA left 8 bits for aggregate check value
  return((sumA <<8) | sumB); // Return checksum value
}


// ----------------------
// Example from section 6.6.2 
// Dual-sum without division
// dataWord: data word in 8-bit blocks
// dwSize:   number of blocks in the data word
// modulus:  modulus for both running sums

uint32_t DualSum16_B(uint8_t dataWord[],
                     uint32_t dwSize, uint32_t modulus) 
{ 
  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all bytes in data word
  for(uint32_t index = 0; index < dwSize; index++)
  { 
    // Add next data word byte with modulus
    sumA = sumA + (uint32_t)dataWord[index];
    while (sumA >= modulus) { sumA -= modulus; }

    sumB = (sumB + sumA);
    while (sumB >= modulus) { sumB -= modulus; }
  }

  return((sumA <<8) | sumB); // Return checksum value
}


// ----------------------
// Example from section 6.6.3  
// Delayed sumB modulo
// dataWord: data word in 8-bit blocks
// dwSize:   number of blocks in the data word
// modulus:  modulus for both running sums

uint32_t DualSum16_C(uint8_t dataWord[],
                     uint32_t dwSize, uint32_t modulus) 
{ 
  assert(dwSize <= 0xFFFFFF); // avoid overflow

  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all bytes in data word
  for(uint32_t index = 0; index < dwSize; index++)
  { 
    // Add next data word byte with modulus
    sumA = (sumA + (uint32_t)dataWord[index])% modulus;
    // Delay sumB modulus until after loop
    sumB = (sumB + sumA);
  }

  sumB = sumB % modulus;

  // Shift sumA left 8 bits for aggregate check value
  return((sumA <<8) | sumB); // Return checksum value
}


// ----------------------
// Example from section 6.6.4 
// Periodic sumA and sumB modulo
// dataWord: data word in 8-bit blocks
// dwSize:   number of blocks in the data word
// modulus:  modulus for both running sums

uint32_t DualSum16_D(uint8_t dataWord[],
                     uint32_t dwSize, uint32_t modulus) 
{ 
  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all bytes in data word
  for(uint32_t index = 0; index < dwSize; index++)
  { 
    // Add next data word byte with modulus
    sumA = (sumA + (uint32_t)dataWord[index]);
    sumB = (sumB + sumA);

    uint32_t const everySixteenth = 0x0F;
    // Modulo on iterations 15, 31, 47, 63, …
    if((index & 0x0F) == everySixteenth)
    {
      sumA = sumA % modulus;
      sumB = sumB % modulus;
    }
  }

  // Final modulo in case length was not 15, 31, 47, …
  sumA = sumA % modulus;
  sumB = sumB % modulus;

  // Shift sumA left 8 bits for aggregate check value
  return((sumA <<8) | sumB); // Return checksum value
}

// ----------------------
// Example from section 6.6.5 
// Adaptive sumA and sumB modulo
// dataWord: data word in 8-bit blocks
// dwSize:   number of blocks in the data word
// modulus:  modulus for both running sums

uint32_t DualSum16_E(uint8_t dataWord[],
                     uint32_t dwSize, uint32_t modulus) 
{ 
  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all bytes in data word
  for(uint32_t index = 0; index < dwSize; index++)
  { 
    // Add next data word byte with modulus
    sumA = (sumA + (uint32_t)dataWord[index]);
    sumB = (sumB + sumA);

    // Time for a modulo if sumB is saturated
    const uint32_t topBits = 0xC0000000;
    if((sumB & topBits) != 0)
    {
      sumA = sumA % modulus;
      sumB = sumB % modulus;
    }
  }

  // Final deferred modulo
  sumA = sumA % modulus;
  sumB = sumB % modulus;

  // Shift sumA left 8 bits for aggregate check value
  return((sumA <<8) | sumB); // Return checksum value
}

// ----------------------
// Example from section 6.6.6 
// Optimized Fletcher Checksum
// dataWord: data word in 8-bit blocks
// dwSize:   number of blocks in the data word
// modulus:  modulus for both running sums

uint32_t Fletcher16(uint8_t dataWord[],
                    uint32_t dwSize, uint32_t modulus) 
{ 
  const uint32_t fletcherModulus = 255;
  assert(modulus == fletcherModulus);  
  const uint32_t bottomMask  = 0x000000FF;
  const uint32_t bitsPerByte = 8;

  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all bytes in data word
  for(uint32_t index = 0; index < dwSize; index++)
  { 
    // Add next data word byte with modulus
    sumA = (sumA + (uint32_t)dataWord[index]);
    sumB = (sumB + sumA);

    // Check for too many carry bits (sumB always worse)
    const uint32_t topBits = 0xC0000000;
    if((sumB & topBits) != 0)
    { sumA = (sumA & bottomMask) 
             + (sumA >> bitsPerByte);
      sumB = (sumB & bottomMask) 
             + (sumB >> bitsPerByte);
    }
  }

  // Wrap around any remaining carry-outs
  while(sumA > bottomMask)
  { sumA = (sumA & bottomMask)
           + (sumA >> bitsPerByte);
  }
  while(sumB > bottomMask)
  { sumB = (sumB & bottomMask) 
           + (sumB >> bitsPerByte);
  }

  // Shift sumA left 8 bits for aggregate check value
  return((sumA <<bitsPerByte) | sumB);
}

// ----------------------
// Example from section 6.6.7 
// DualX adaptive modulo with 16-bit block processing
// dataWord: data word in 8-bit blocks processed
// dwSize:   number of 8-bit blocks in the data word
// modulus:  modulus for both running sums

uint32_t DualX(uint8_t dataWord[],
                     uint32_t dwSize, uint32_t modulus) 
{ 
  assert(modulus == 253);
  assert((dwSize & 1) == 0);    // Even number of bytes
  uint32_t sumA = initialSeed;  // Initialize sumA
  uint32_t sumB = initialSeed;  // Initialize sumB
  
  // Loop over all 16-bit blocks in data word
  const uint32_t  blockSize = 2;
  for(uint32_t index = 0; index < dwSize;
                                    index += blockSize)
  { 
    // Add next data word byte with modulus
    uint32_t block = (((uint32_t)dataWord[index+1])<<0)
                   | (((uint32_t)dataWord[index+0])<<8);

    sumA = (sumA + block);
    sumB = (sumB + sumA);

    // Time for a modulo if sumB is saturated
    const uint32_t topBits = 0xC0000000;
    if((sumB & topBits) != 0)
    {
      sumA = sumA % modulus;
      sumB = sumB % modulus;
    }
  }

  // Final deferred modulo
  sumA = sumA % modulus;
  sumB = sumB % modulus;

  // Shift sumA left 8 bits for aggregate check value
  return((sumA <<8) | sumB); // Return checksum value
}