#! Prepares the top of the stack with the hasher initial state.
#!
#! This procedures does not handle padding, therefore, the user is expected to
#! consume an amount of data which is a multiple of the rate (2 words).
#!
#! Input: []
#! Ouptut: [PERM, PERM, PERM, ...]
#!
#! Cycles: 12
export.init_no_padding
   padw padw padw
end

#! Given the hasher state, returns the hash output.
#!
#! Input: [C, B, A, ...]
#! Ouptut: [HASH, ...]
#!
#! Where :
#! - `A` is the capacity word that will be used by the hashing function.
#! - `B` is the hash output.
#!
#! Cycles: 9
export.squeeze_digest
  # drop the first rate word (4 cycles)
  dropw

  # save the hash result (1 cycles)
  swapw

  # drop the capacity word (4 cycles)
  dropw
end

#! Hashes the memory `start_addr` to `end_addr` given an RPO state specified by 3 words.
#!
#! This requires that `end_addr = start_addr + 2n` where n = {0, 1, 2 ...}, otherwise the procedure 
#! will enter an infinite loop. 
#!
#! Input: [C, B, A, start_addr, end_addr, ...]
#! Output: [C', B', A', end_addr, end_addr ...]
#!
#! Where :
#! - `A` is the capacity word that will be used by the hashing function.
#! - `B` is the hash output.
#!
#! Cycles: 4 + 3 * words, where `words` is the `start_addr - end_addr`
export.absorb_double_words_from_memory
  dup.13 dup.13 neq  # (4 cycles )
  while.true
    mem_stream hperm # (2 cycles)
    dup.13 dup.13 neq  # (4 cycles )
  end
end

#! Hashes the memory `start_addr` to `end_addr`, handles odd number of elements.
#!
#! Requires `start_addr ≤ end_addr`, `end_addr` is not inclusive.
#!
#! Input: [start_addr, end_addr, ...]
#! Output: [H, ...]
#!
#! Cycles:
#! - even words: 49 cycles + 3 * words
#! - odd words: 61 cycles + 3 * words
#! where `words` is the `start_addr - end_addr - 1`
export.hash_memory_words
  # enforce `start_addr ≤ end_addr`
  dup.1 dup.1 u32assert2 u32gte assert

  # figure out if the range is for an odd number of words (9 cycles)
  dup.1 dup.1 sub is_odd
  # => [is_odd, start_addr, end_addr, ...]

  # make the start/end range even (4 cycles)
  movup.2 dup.1 sub
  # => [end_addr, is_odd, start_addr, ...]

  # move start_addr to the right stack position (1 cycles)
  movup.2
  # => [start_addr, end_addr, is_odd, ...]

  # prepare hasher state (14 cycles)
  dup.2 mul.4 push.0.0.0 padw padw
  # => [C, B, A, start_addr, end_addr, is_odd, ...]

  # (4 + 3 * words cycles)
  exec.absorb_double_words_from_memory
  # => [C', B', A', end_addr, end_addr, is_odd, ...]

  # (1 cycles)
  movup.14
  # => [is_odd, C', B', A', end_addr, end_addr, ...]

  # handle the odd element, if any (12 cycles)
  if.true
    # start_addr and end_addr are equal after calling `absorb_double_words_from_memory`, and both 
    # point to the last element. Load the last word (6 cycles)
    dropw dup.9 mem_loadw
    # => [D, A', end_addr, end_addr, ...]

    # set the padding and compute the permutation (5 cycles)
    padw hperm
  end

  exec.squeeze_digest
  # => [HASH, end_addr, end_addr, ...]

  # drop start_addr/end_addr (4 cycles)
  movup.4 drop movup.4 drop
  # => [HASH]
end

#! Computes hash of Felt values starting at the specified memory address.
#!
#! This procedure divides the hashing process into two parts: hashing pairs of words using 
#! `absorb_double_words_from_memory` procedure and hashing the remaining values using the `hperm`
#! instruction. 
#!
#! Inputs:  [ptr, num_elements]
#! Outputs: [HASH]
#!
#! Cycles: 
#! - If number of elements divides by 8: 47 cycles + 3 * words
#! - Else: 180 cycles + 3 * words
#! where `words` is the number of quads of input values.
export.hash_memory
    # move number of inputs to the top of the stack 
    swap
    # => [num_elements, ptr]

    # get the number of double words
    u32divmod.8 swap
    # => [num_elements/8, num_elements%8, ptr]

    # get the end_addr for hash_memory_even procedure (end address for pairs of words)
    mul.2 dup.2 add movup.2
    # => [ptr, end_addr, num_elements%8]

    # get the capacity element which is equal to num_elements%8
    dup.2
    # => [capacity, ptr, end_addr, num_elements%8]
    
    # prepare hasher state for RPO permutation 
    push.0.0.0 padw padw 
    # => [C, B, A, ptr, end_addr, num_elements%8]

    # hash every pair of words
    exec.absorb_double_words_from_memory
    # => [C', B', A', ptr', end_addr, num_elements%8] where ptr' = end_addr

    # hash remaining input values if there are any left
    # if num_elements%8 is ZERO and there are no elements to hash
    dup.14 eq.0
    if.true
      # clean the stack
      exec.squeeze_digest
      swapw drop drop drop movdn.4
      # => [B']
    else
      # load the remaining double word
      mem_stream
      # => [E, D, A', ptr'+2, end_addr, num_elements%8]

      # clean the stack
      movup.12 drop movup.12 drop
      # => [E, D, A', num_elements%8]

      # get the number of elements we need to drop
      # notice that drop_counter could be any number from 1 to 7
      push.8 movup.13 sub movdn.12
      # => [E, D, A', drop_counter]

      ### 0th value ########################################################
      
      # we need to drop first value anyway, since number of values is not divisible by 8
      # push the padding 0 on to the stack and move it down to the 6th position 
      drop push.0 movdn.6
      # => [e_2, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', drop_counter]

      ### 1st value ########################################################

      # prepare the second element of the E Word for cdrop instruction
      push.0 swap
      # => [e_2, 0, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', drop_counter]

      # push latch variable onto the stack; this will be the control for the cdrop instruction
      push.0
      # => [latch = 0, e_2, 0, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', drop_counter]

      # get the flag whether the drop counter is equal 1
      dup.14 eq.1
      # => [drop_counter == 1, latch = 0, e_2, 0, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', drop_counter]

      # update the latch: if drop_counter == 1, latch will become 1
      or
      # => [latch', e_2, 0, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', drop_counter]

      # save the latch value 
      dup movdn.14
      # => [latch', e_2, 0, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', latch', drop_counter]

      # if latch == 1, drop 0; otherwise drop e_1
      cdrop
      # => [e_2_or_0, e_1, e_0, d_3, d_2, d_1, 0, d_0, A', latch', drop_counter]

      # move the calculated value down the stack 
      movdn.6
      # => [e_1, e_0, d_3, d_2, d_1, 0, e_2_or_0, d_0, A', latch', drop_counter]

      ### 2nd value ########################################################

      # repeat the above process but now compare drop_counter to 2
      push.0 swap
      movup.13 dup.14 eq.2 or
      dup movdn.14
      cdrop movdn.6
      # => [e_0, d_3, d_2, d_1, 0, e_2_or_0, e_1_or_0, d_0, A', latch', drop_counter]

      ### 3rd value ########################################################

      # repeat the above process but now compare drop_counter to 3
      push.0 swap
      movup.13 dup.14 eq.3 or
      dup movdn.14
      cdrop movdn.6
      # => [d_3, d_2, d_1, 0, e_2_or_0, e_1_or_0, e_0_or_0, d_0, A', latch', drop_counter]

      ### 4th value ########################################################

      # repeat the above process but now compare drop_counter to 4
      push.0 swap
      movup.13 dup.14 eq.4 or
      dup movdn.14
      cdrop movdn.6
      # => [d_2, d_1, 0, e_2_or_0, e_1_or_0, e_0_or_0, d_3_or_0, d_0, A', latch', drop_counter]

      ### 5th value ########################################################

      # repeat the above process but now compare drop_counter to 5
      push.0 swap
      movup.13 dup.14 eq.5 or
      dup movdn.14
      cdrop movdn.6
      # => [d_1, 0, e_2_or_0, e_1_or_0, e_0_or_0, d_3_or_0, d_2_or_0, d_0, A', latch', drop_counter]

      ### 6th value ########################################################

      # repeat the above process but now compare drop_counter to 6
      push.0 swap
      movup.13 movup.14 eq.6 or
      cdrop movdn.6
      # => [0, e_2_or_0, e_1_or_0, e_0_or_0, d_3_or_0, d_2_or_0, d_1_or_0, d_0, A']
      # or in other words
      # => [C, B, A', ... ]
      # notice that we don't need to check the d_0 value: entering the else branch means that 
      # we have number of elements not divisible by 8, so we will have at least one element to 
      # hash here (which turns out to be d_0)

      hperm
      # => [F, E, D]

      exec.squeeze_digest
      # => [E]
    end
end