#include <cstddef>
#include <cstdint>
#include <iostream>

// We have looked at two hash functions.
//
// Here we will look at three more. These use
// bit-shifting techniques. You will be asked
// to implement each.
//
// All three functions operate on 32-bit unsigned
// integers.
//
// CRC-style variant:
//
// In the previous example, we multiplied the
// current hash value by a prime number.
//
// In this case, we will rotate the previous
// 32-bit value to the left by seven bits:
//
//     BBBBBBBbbbbbbbbbbbbbbbbbbbbbbbbb
//           /\
//    BBBBBBB  bbbbbbbbbbbbbbbbbbbbbbbbb
//     \\\\\\\ ////////////////////////
//      \\\\\\\___________ ///////////
//           //////////// \ /////////
//          ////////////// \ ///////
//         //////////////// \ /////
//        ////////////////// \ ///
//       //////////////////// \ /
//      ////////////////////// \
//     //////////////////////// \\\\\\\
//    bbbbbbbbbbbbbbbbbbbbbbbbbBBBBBBB
//
// Next, XOR the next character with this result:
//
//    bbbbbbbbbbbbbbbbbbbbbbbbbBBBBBBB
//                             ^ xxxxxxxx
//    --------------------------------
//    cccccccccccccccccccccccccccccccc
//
// Repeat this for each character.
//
//
// PJW:
//
// In this example, the leftmost four bits are
// initially zero:
//
//    0000bbbbbbbbbbbbbbbbbbbbbbbbbbbb
//
// First, shift the value four bits to the left:
//
//    bbbbbbbbbbbbbbbbbbbbbbbbbbbb0000
//
// Then add the next character:
//
//                          + xxxxxxxx
//    --------------------------------
//    CCCCcccccccccccccccccccccccccccc
//
// Extract the leftmost four bits:
//
//    CCCC0000000000000000000000000000
//
// Move those four bits to the right:
//
//    0000000000000000000000000000CCCC
//
// Clear the leftmost four bits of the hash value:
//
//    0000cccccccccccccccccccccccccccc
//
// and XOR the extracted four bits into the result:
//
//    0000cccccccccccccccccccccccccccc
//                             ^ CCCC
//    --------------------------------
//    0000dddddddddddddddddddddddddddd
//
// Repeat this for each character.
//
//
// BUZ:
//
// This hash rotates the current value to the left
// by one bit:
//
//    Bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
//     \____________________________
//                                  \
//    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbB
//
// Next, XOR the result with a value obtained from
// the next character:
//
//    value ^= character*1779033705
//
// and repeat for each character.
//
// The constant 1779033705 is a 32-bit value chosen
// to mix the bits of each character into the hash.
//
//
// Bit shifting can be performed very efficiently
// in hardware. You will see more of these operations
// in ECE 124 and ECE 222.
//
// Reference:
// https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html

// Function declarations
std::uint32_t crc_hash( char const *str );
std::uint32_t pjw_hash( char const *str );
std::uint32_t buz_hash( char const *str );

int main();

// Function definitions
int main() {
    char const *str{
        "Yesterday is but today's memory, "
        "and tomorrow is today's dream."
    };

    std::cout << crc_hash( str ) << std::endl;
    std::cout << pjw_hash( str ) << std::endl;
    std::cout << buz_hash( str ) << std::endl;

    return 0;
}

std::uint32_t crc_hash( char const *str ) {
    std::uint32_t value{ 0 };

    // Enter your implementation here.

    return value;
}

std::uint32_t pjw_hash( char const *str ) {
    std::uint32_t value{ 0 };

    // Enter your implementation here.

    return value;
}

std::uint32_t buz_hash( char const *str ) {
    std::uint32_t value{ 0 };

    // Enter your implementation here.

    return value;
}































// Hint:
//
// Perform each operation one step at a time.
//
// For the CRC-style hash:
//
//   1. Save the leftmost seven bits.
//   2. Move those seven bits to the right.
//   3. Shift the hash value seven bits to the left.
//   4. XOR the saved bits into the hash value.
//   5. XOR the next character into the hash value.
//
// For the PJW hash:
//
//   1. Shift the hash value four bits to the left.
//   2. Add the next character.
//   3. Save the leftmost four bits.
//   4. Move those four bits to the right.
//   5. Clear the leftmost four bits.
//   6. XOR the saved bits into the hash value.
//
// For the BUZ hash:
//
//   1. Save the leftmost bit.
//   2. Move that bit to the right.
//   3. Shift the hash value one bit to the left.
//   4. XOR the saved bit into the hash value.
//   5. Multiply the next character by 1779033705.
//   6. XOR that result into the hash value.































// Here are three solutions:

/*
std::uint32_t crc_hash( char const *str ) {
    std::uint32_t value{ 0 };

    for ( std::size_t k{ 0 }; str[k] != '\0'; ++k ) {
        std::uint32_t top_bits{ value & 0xFE000000u };

        top_bits >>= 25;
        value <<= 7;
        value ^= top_bits;
        value ^= static_cast<unsigned char>( str[k] );
    }

    return value;
}

std::uint32_t pjw_hash( char const *str ) {
    std::uint32_t value{ 0 };

    for ( std::size_t k{ 0 }; str[k] != '\0'; ++k ) {
        value <<= 4;
        value += static_cast<unsigned char>( str[k] );

        std::uint32_t top_four_bits{
            value & 0xF0000000u
        };

        top_four_bits >>= 28;
        value &= 0x0FFFFFFFu;
        value ^= top_four_bits;
    }

    return value;
}

std::uint32_t buz_hash( char const *str ) {
    std::uint32_t value{ 0 };

    for ( std::size_t k{ 0 }; str[k] != '\0'; ++k ) {
        std::uint32_t top_bit{ value & 0x80000000u };

        top_bit >>= 31;
        value <<= 1;
        value ^= top_bit;

        value ^= 1779033705u
                 * static_cast<unsigned char>( str[k] );
    }

    return value;
}
*/