1 answer

1 Objective Build a hashing algorithm that is suitable for use in a Bloom Filter. Please...

Question:

1 Objective Build a hashing algorithm that is suitable for use in a Bloom Filter. Please note that while a cryptographic hash

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 [email protected]:"/cop3503/hw3 $ java Hw03 5words.txt ff210377;3.5;18.5 25e69846: aaaa c3bef462:bbbbbbbbb c6e29ee2:ccccccccddddddeeeeffff d633fb53: bananas 7a8fa153: syzygy Input file processed [email protected]:"/cop3503/hw3 $java Hw03 5words.txt >5wordsSt.txt ff210377;3.5;18.5 [email protected]:"/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.

Answers

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");
}
}

.

Similar Solved Questions

1 answer
An individual with an income of 1000 is considering the purchase of a risky asset for...
An individual with an income of 1000 is considering the purchase of a risky asset for $250. There is a 40% chance the asset will earn $1000 and a 60% chance it will be worthless. a. Will the individual purchase this asset? b. What is the cost of risk for this individual if the asset is purchased? c....
1 answer
Average Diast Blood Pressure 58 Average Diast Blood Pressure 58 Stem-and-Leaf Plot Frequency    Stem & Leaf...
Average Diast Blood Pressure 58 Average Diast Blood Pressure 58 Stem-and-Leaf Plot Frequency    Stem & Leaf       .00        6 .      7.00        6 . 5558889  &n...
1 answer
If the business were to over-report Rent Expenses by $5,000 what would this do to the...
If the business were to over-report Rent Expenses by $5,000 what would this do to the Net Income figure? (Ctrl)- FASTFORWARD Income Statement For Month Ended December 31, 2018 Revenues Consulting revenue ($4,200 + $1,600) Rental revenue Total revenues Expenses Rent expense Salaries expense Total exp...
1 answer
Draw a synthesis of phenacetin that employs acetic anhydride, with mechanism.
Draw a synthesis of phenacetin that employs acetic anhydride, with mechanism....
1 answer
Figure 1 Q 3. For the circuit in figure 2 find Vo/V. (25 Points) R, 2...
Figure 1 Q 3. For the circuit in figure 2 find Vo/V. (25 Points) R, 2 Figure 2 Q4. Design a differentiator circuit as shown in figure 3 to give /u - 10 kHz and Jir- 20 KHZ The pass b (APBI = 25. (25 Points)...
1 answer
Although dividends are not an expense of a company, they still impact retained earnings. Select one:...
Although dividends are not an expense of a company, they still impact retained earnings. Select one: O a. TRUE O b. FALSE...
1 answer
Puget Sound Divers is a company that provides diving services such as underwater ship repairs to...
Puget Sound Divers is a company that provides diving services such as underwater ship repairs to clients in the Puget Sound area. The company’s planning budget for May appears below: Puget Sound Divers Planning Budget For the Month Ended May 31 Budgeted diving-hours (q) 300 Revenu...
1 answer
The sum of the page numbers of Chapter 3 (of a certain book) is 374. If there are 11 pages in Chapter 3, on what page does Chapter 3 begin?
The sum of the page numbers of Chapter 3 (of a certain book) is 374. If there are 11 pages in Chapter 3, on what page does Chapter 3 begin?...
1 answer
On August 1, Delta Corp. received $2,000 cash for providing services to a customer. On August...
On August 1, Delta Corp. received $2,000 cash for providing services to a customer. On August 30, the customer returned one-fourth of the inventory back to Delta for a cash refund. Required: In the general journal below, record each of the above transactions. Note: Do not use decimals, currency symb...
1 answer
A car radio draws 0.25 A of current in the auto's 12 V electrical system. (a) How much electric...
A car radio draws 0.25 A of current in the auto's 12 V electrical system.(a) How much electric power does the radio use?----------- W(b) What is the effective resistance of the radio?...
1 answer
14% of all Americans live in poverty. If 41 Americans are randomly selected, find the probability...
14% of all Americans live in poverty. If 41 Americans are randomly selected, find the probability that a. Exactly 3 of them live in poverty. b. At most 4 of them live in poverty. c. At least 4 of them live in poverty. d. Between 2 and 9 (including 2 and 9) of them live in poverty,...
1 answer
Question 8 1 pts Suppose that a firm's capital is composed of 80% common equity and...
Question 8 1 pts Suppose that a firm's capital is composed of 80% common equity and 20% percent debt (no preferred stock is used). In addition, the before-tax cost of debt is 5%, the cost of equity is 10%, and the firm's marginal tax rate is 21%. The firm's weighted average cost of capit...
1 answer
A manufacturer sells paperback books in their retail stores and wanted to examine the relationship between...
A manufacturer sells paperback books in their retail stores and wanted to examine the relationship between price and demand. The price of a particular novel was adjusted each week and the weekly sales were recorded in the accompanying table. Management would like to use simple regression analysis to...
1 answer
Ex. 10 Annie and Alvie have agreed to meet between 5:00 P.M. and 6:00 P.M. for dinner at a local health-food restaurant. Let X = Annie's arrival time and Y= Alvie's arrival time. Suppose X and Yare independent with each uniformly distributed on the interv
Ex. 10Annie and Alvie have agreed to meet between 5:00 P.M. and 6:00 P.M. for dinner at a local health-food restaurant. Let X = Annie's arrival time and Y= Alvie's arrival time. Suppose X and Yare independent with each uniformly distributed on the interval [5, 6].a. What is the joint pdf of ...
1 answer
2. Given: [ 3x2(t) + 2x3t) x(t) - 4x1(t) + x2(t) ] Find, (a) use any...
2. Given: [ 3x2(t) + 2x3t) x(t) - 4x1(t) + x2(t) ] Find, (a) use any method taught in class to determine the stability of the nonlinear system...
2 answers
How do you solve #-11- 2x = - x + 25#?
How do you solve #-11- 2x = - x + 25#?...
3 answers
Suppose an unknown substance has a melting temperature of 1,200 degrees Celsius and a density of 16.7 g/cm3
Suppose an unknown substance has a melting temperature of 1,200 degrees Celsius and a density of 16.7 g/cm3. However, the different individual atoms that make up the element have very different melting temperatures and densities. The unknown substance is most likely a what?...
1 answer
DNA Electrophoresis a) Find terminal velocity in um/s b)  Draw a FBD (free-body diagram) for the DNA...
DNA Electrophoresis a) Find terminal velocity in um/s b)  Draw a FBD (free-body diagram) for the DNA molecule in the gel Our Gel: Information about the gel in Figure 1: • Run Time: 105 minutes. • The DNA sample contained 13 different sizes of DNA molecules (Table 1). The appara...