Question

1 Objective Build a hashing algorithm that is suitable for use in a Bloom Filter. Please note that while a cryptographic hash is quite common in many Bloom Filters, the hashing algorithm to be implemented is a mix of the the following algorithmic models, specifically, a multiply & rotate hash colloquially known as a murmur hash, and an AND, rolale, & XOR hash colloquially known as an ARX hash. 2 Requirements • Inputs. Read the input file which contains strings of characters, with one string per line. Please note that the strings may vary in size from a single character to many characters, perhaps as long as 35 characters and may be possibly longer. * All the input characters will be in 8 bit ASCII not UTF. Calculate the hash value for the single string in the particular line under test. 2.1 Algorithm Design The pseduocode for the acram hashing algorithm is shown below. Please note the following: • The input string is in ASCII in either a Java string or as an array of characters in bytes. . Once the the single word has been read, therram function calculates the 32 bit integer hash value derived from the input text. • Upon completion of the hash calculation, the hash value is output as specified in the Outputs section. 7 8 9 10: 11: 12: Algorithm 1xram(String input, int len) 1: randVall Oubcde98ef // aribtrary value 2: randVal2 + 0x7890 face 3: hashVal + 0x fa01bc96 // start seed value 4: roundedEnd + len & 0xfffffffc // Array d gets 4 byte blocks 5: for i=0;i< roundedEnd; i + 4 do 6: tempData + (d[i] & 0xf!) I ((d[1 + 1] & 0xf/) << 8)| ((datafi + 2) & 0xfD) << 16) 1 (di +3] << 24 tempdata -- temp Data * randVall // Mulitiply ROT L(tempData, 12) // Rotate left 12 bits tempdata + tempData + rand Val2 // Another Multiply hashValue hashValue tempData ROTL(hashValue, 13) // Rotate left 13 bits hashValue + hashValue + 5 + 0.3-46b6456e // Now collect orphan input characters 13: tempData 0 14: if (len & 0x03) == 3) then 15: tempData +- (data[rounded End + 2 & 0xff) << 16 16: len len 1 17: if (len & 0x03) -- 2) then tempData = (data[roundedEnd + 11 & 0xff) <<8 + len 20: if (len & 0x03) == 1) then tempData | – (data[roundedEnd & Oxff) tempData + tempData = randVall // Multiply ROTI tempData, 14) // Rotate left 14 bits 24: tempData * randVal2 // Another Multiply 25: hashValue + hashValue o 26: hashValue + hashValue • len // XOR 27: hashValue < hashValue & 0.cb6acbe58 28: hashValue hashValue 0 hashValue >>> 13 29. hashValue + hashValue 0353ea2b2c // Another arbitrary value 30: hashValue hash Value hash Value >>> 16 31: RETURN hash Value // Return the 32 bit int hash 18: 19: 1 21: 22: 23: tempData // AND 2.1.1 Outputs The output of the cram hashing algorithm is deceptively simple and shown below. Hash Value System.out.format("%10x: %s\n", hashValue, input ); Completion System.out.println("Input file processed"); 2.1.2 Functions complexity Indicator Prints to STDERR the following: NID A difficulty rating of difficult you found this assignment on a scale of 1.0 (casy-pcasy) through 5.0 (knuckle busting degree of difficulty). Duration, in hours, of the time you spent on this assignment. Sample output: ff210377Qeustis: "/COP3503$ ff210377;3.5;18.5 3 Testing Make sure to test your code on Eustis even if it works perfectly on your machine. If your code does not compile on Eustis you will receive a 0 for the assignment. There will be 10 input files and 9 output files provided for testing your code, they are respectively shown in Table and in Table Filename Description one A.txt A single upper case A two As.txt Two upper case As three As.txt Three upper case As fourAs.txt Four upper case As 5words.txt 5 words 100words.txt 100 words 500words.txt 500 words 1000 words.txt 1000 words 2500 words.txt 2500 words Table 1: Input files The expected output for these test cases will also be provided as defined in Table 2 To compare your output to the expected output you will first need to redirect STDOUT to a text file. Run your code with the following command (substitute the actual names of the input and output file appropriately): java Hw03 inputFile > output.txt The run the following command (substitute the actual name of the expected output file): diff output.txt expectedOutputFile If there are any differences the relevant lines will be displayed (note that even a single extra space will cause a difference to be detected). If nothing is displayed, then congratulations - the outputs match! For each of the five (5) test cases, your code will need to output to STDOUT text that is identical to the corresponding expected OutputPilc. If your code crashes for a particular test case, you will not get credit for that case. 4 Submission - via Web Courses The Java source file, named Hw03.java. Make sure that the main program is in Hw03.java. Use reasonable and customary naming conventions for any classes you may create for this assignment. 5 Sample output ff210377@eustis:"/cop3503/hw3 $ java Hw03 5words.txt ff210377;3.5;18.5 25e69846: aaaa c3bef462:bbbbbbbbb c6e29ee2:ccccccccddddddeeeeffff d633fb53: bananas 7a8fa153: syzygy Input file processed ff210377@eustis:"/cop3503/hw3 $java Hw03 5words.txt >5wordsSt.txt ff210377;3.5;18.5 ff210377@eustis:"/cop3503/hw3 $ diff 5wordsSt.txt 5wordsValid.txt ff210377Qeustis:"/cop3503/hw3 $ Note: This is based on an actual UCFram outpul using the inpuls specified in the com- mands shown above. Note The ff210377;3.5;18.5 output shown above is the output from the complexityIndi- calor function to STDERR. Command Validly formatted output files java Hw03 oneA.txt > one ASt.txt one AValid.txt java Hw03 twoAs.txt > twoAsSt.txt twoAsValid.txt java Hw03 three As.txt > three AsSt.txt threeAsValid.txt java Hw03 four As.txt > four Asst.txt four AsValid.txt java Hw03 5words.txt > 5wordsSt.txt 5wordsValid.txt java Hw03 100words.txt > 100wordsSt.txt 100wordsValid.txt java Hw03 500words.txt > 500wordsSt.txt 500wordsValid.txt java Hw03 1000words.txt > 1000wordsSt.txt 1000wordsValid.txt java Hw03 2500words.txt > 2500wordsSt.txt 2500wordsValid.txt Table 2: Commands with input files and corresponding output files.

Answer 1

import java.io.*;
import java.util.*;

class Hw03
{

public static int xram(String input, int length)
   {
int rand1 = 0xbcde98ef;
int rand2 = 0x7890face;
int hashValue = 0xfa01bc96;
int roundedEnd = (length & 0xfffffffc);
int tmpData = 0; //how do i initialize?

int[] data = new int[length];
for(int i=0; i<length; i++)
       {
data[i] = (int)input.charAt(i);
}

for(int i=0; i<roundedEnd; i+=4)
       {
tmpData = (data[i] & 0xff)|((data[i+ 1] & 0xff)<<8)|((data[i+ 2] & 0xff)<<16)|(data[i+ 3]<<24);
tmpData *= rand1;
tmpData = Integer.rotateLeft(tmpData,12);
tmpData *= rand2;
hashValue = hashValue ^ tmpData;
hashValue = Integer.rotateLeft(hashValue,13);
hashValue = (hashValue * 5) + 0x46b6456e;
}
tmpData = 0;

if((length & 0x03) == 3)
       {
tmpData = (data[roundedEnd + 2] & 0xff) << 16;
length -= 1;
}
if((length & 0x03) == 2)
       {
  
tmpData |= (data[roundedEnd + 1] & 0xff) << 8;
length -= 1;
}
if((length & 0x03) == 1)
       {
tmpData = tmpData | (data[roundedEnd] & 0xff);
tmpData = tmpData * rand1;
tmpData = Integer.rotateLeft(tmpData,14);
tmpData = tmpData * rand2;
hashValue = hashValue ^ tmpData;
}

hashValue = hashValue ^ length;
hashValue = hashValue & 0xb6acbe58;
hashValue = hashValue ^ hashValue >>> 13;
hashValue = hashValue * 0x53ea2b2c;
hashValue = hashValue ^ hashValue >>> 16;

System.out.format("%10x:%s\n",hashValue, input);

return hashValue;
}

public static void complexityIndicator()
   {
System.err.println("al144291;4;4");
}
  
public static void main(String[] args) throws Exception
{
complexityIndicator();

String infile = args[0];
Scanner scnr = new Scanner(new File(infile));

while(scnr.hasNext())
       {
String line = scnr.nextLine();
int length = line.length();
xram(line, length);
}
System.out.println("Input file processed");
}
}