/// LSU EE 4720 -- Computer Architecture
//
//  Reference code for 2019 Homework 1.
//  Assignment https://www.ece.lsu.edu/ee4720/2019/hw01.pdf
//  Put solution in file hw01.s.

#include <stdio.h>
#include <string.h>
#include <vector>
#include <cstdint>

using namespace std;

const int hash_lg = 8;
const int hash_size = 1 << hash_lg;
const int hash_mask = hash_size - 1;

const char* const words =
  "aardvark\0"
  "ark\0"
  "bark\0"
  "barkeeper\0"
  "persevere\0"
  "bird\0"
  "box\0"
  "sox\0"
  "lox\0"
  "soy\0"
  "sax\0"
  "brain\0"
  "\0";

const char* test_words[] =
 {
  "ark",
  "box", "sox", "soy", "sax", "sod",
  "barkeeper",
  "bark",
  "woof",
  "bar",
  "ark",
  "bar",
  "bark",
  "barkeeper",
  "arkansas",
  "lox", "box", "sox", "sax", "soy",
  "aardvark",
  "persevere"
 };

struct Hash_Elt {
  int16_t offset;
  int16_t pos;
};


class App
{
public:
  App():hash_table(hash_size){};
  vector<Hash_Elt> hash_table;

  int hash_func(const char* str)
    {
      return
        ( str[0] ^ ( str[1] >> 2 ) ^ ( str[1] << 6 ) ^
        ( str[2] << 4 ) ^ ( str[2] >> 4 ) ) & hash_mask;
    }

  bool streq(const char* s1, const char* s2)
    {
      while ( *s1 && *s2 ) if ( *s1++ != *s2++ ) return false;
      return *s1 == *s2;
    }

  struct Lookup_Info {
    int pos, hash;
    bool in_hash;
  };

  void lookup_msg(const char *word)
  {
    Lookup_Info li = lookup(word);
    printf("Hash %#04x  Idx %2d  In Hash %s  Word %s\n",
           li.hash, li.pos, li.in_hash ? "YES" : "NO ", word);
  }

  Lookup_Info lookup(const char *word)
  {
    // Look up word in hash table.
    //
    const int hash = hash_func(word);
    Hash_Elt& elt = hash_table[ hash ];

    Lookup_Info li;
    li.hash = hash;

    // Return if hash table hit.
    //
    if ( elt.pos && streq( &words[elt.offset], word ) )
      {
        li.pos = elt.pos;
        li.in_hash = true;
        return li;
      }

    li.in_hash = false;

    // Scan word list to find word.
    //
    int offset = 0;
    int pos = 0;
    while ( words[offset] )
      {
        pos++;
        if ( streq( &words[offset], word ) )
          {
            // Word has been found, add to hash table and return index.
            elt.offset = offset;
            li.pos = elt.pos = pos;
            return li;
          }

        // Word not found, advance to next word. Assembler can be faster.
        offset += strlen( &words[offset] ) + 1;
      }

    // Word not in word list, return 0.
    li.pos = 0;
    return li;
  }

  void hw01_tables_write()
  {
     vector<const char*> wordsv;
     for ( const char *wptr = words; *wptr; wptr += 1 + strlen(wptr) )
       wordsv.push_back( wptr );

     printf("word_list_start:\n");
     for ( auto w: wordsv ) printf("\t.asciiz \"%s\"\n",w);
     printf("word_list_end:\ntest_words_start:\n");
     for ( auto w: test_words ) printf("\t.asciiz \"%s\"\n",w);
     printf(R"--(test_words_end:
        .byte 0 0 0 0
        .align 4
results_start:
)--");
     for ( const char *w: test_words )
       {
        Lookup_Info li = lookup(w);
        printf("\t.word %3d %#5x  # %s\n",
               li.pos, li.in_hash ? li.hash + 0x100 : li.hash, w );
       }
  }

};

int
main(int argc, char **argv)
{
 App app;

 app.hw01_tables_write();

}