source: proiecte/HadoopA51/src/java/ro/pub/cs/pp/a51hadoop/algorithm/testing/DigitReducer.java @ 166

Last change on this file since 166 was 166, checked in by (none), 14 years ago

HadoopA51: imported git repository from github
File size: 2.5 KB
Line 
1package ro.pub.cs.pp.a51hadoop.algorithm.testing;
2
3import ro.pub.cs.pp.a51hadoop.algorithm.HashReducer;
4
5
6/* A reduction function R that maps hash values back into secret values.
7 *
8 * There are many possible implementations for this function, and it's only
9 * important that it behaves pseudorandomly.
10 *
11 * By alternating the hash function with the reduction function,
12 * chains of alternating passwords and hash values are formed.
13 *
14 *
15 * This reducer only changes one digit of the given string
16 * (represented as a number).
17 */
18public class DigitReducer implements HashReducer
19{
20        private int i;
21        private int k;
22        public DigitReducer(int i, int k)
23        {
24                this.i = i;
25                this.k = k;
26        }
27
28        /*
29         * Apply the current Reducer on the given hash.
30         *
31         * @return a new secret value
32         */
33        public String apply(String strX)
34        {
35                try
36                {
37                        int last_digit = 0;
38                        int x = Integer.parseInt(strX);
39
40
41                        /*
42                         * This is a limmited implementation.
43                         *
44                         * It will not give us pseudorandom strings,
45                         * but this will do for testing pourposes.
46                         */
47                        switch (i)
48                        {
49                        case 0:
50                                last_digit = i % 3;
51                                break;
52                        case 1:
53                                last_digit = i % 3 + 3;
54                                break;
55                        case 2:
56                                last_digit = i % 3 + 6;
57                                break;
58                        default:
59                                last_digit = 9;
60                                break;
61                        }
62
63                        /*
64                         * Change the last digit
65                         */
66                        x = x / 10 * 10 + last_digit;
67
68
69                        /*
70                         * This is done to look like we have many
71                         * distinct reducer functions.
72                         *
73                         * This is required to solve the problem of
74                         * collisions with ordinary hash chains by
75                         * replacing the single reduction function R
76                         * with a sequence of related reduction
77                         * functions R1 through Rk.
78                         *
79                         * This way, in order for two chains to
80                         * collide and merge, they must hit the same
81                         * value on the same iteration. Consequently,
82                         * the final values in each chain will be
83                         * identical. A final postprocessing pass can
84                         * sort the chains in the table and remove any
85                         * "duplicate" chains that have the same final
86                         * value as other chains. New chains are then
87                         * generated to fill out the table. These
88                         * chains are not collision-free (they may
89                         * overlap briefly) but they will not merge,
90                         * drastically reducing the overall number of
91                         * collisions
92                         */
93                        x = x ^ k;
94
95                        String ret = "" + x;
96                        while(ret.length() < strX.length())
97                                ret = "0" + ret;
98                        if (ret.length() > strX.length())
99                                ret = ret.substring(0, strX.length());
100                        return ret;
101                }
102                catch (Exception e)
103                {
104                        /*
105                         * On error return the original unmodified
106                         * string.
107                         */
108                        return strX;
109                }
110        }
111}
Note: See TracBrowser for help on using the repository browser.