+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
7.3 KiB297 linesraw
1/**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements.  See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership.  The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License.  You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19package org.apache.hadoop.examples.terasort;
20
21import java.io.DataInput;
22import java.io.DataOutput;
23import java.io.IOException;
24
25import org.apache.hadoop.io.Writable;
26
27/**
28 * An unsigned 16 byte integer class that supports addition, multiplication,
29 * and left shifts.
30 */
31class Unsigned16 implements Writable {
32  private long hi8;
33  private long lo8;
34
35  public Unsigned16() {
36    hi8 = 0;
37    lo8 = 0;
38  }
39
40  public Unsigned16(long l) {
41    hi8 = 0;
42    lo8 = l;
43  }
44
45  public Unsigned16(Unsigned16 other) {
46    hi8 = other.hi8;
47    lo8 = other.lo8;
48  }
49  
50  @Override
51  public boolean equals(Object o) {
52    if (o instanceof Unsigned16) {
53      Unsigned16 other = (Unsigned16) o;
54      return other.hi8 == hi8 && other.lo8 == lo8;
55    }
56    return false;
57  }
58
59  @Override
60  public int hashCode() {
61    return (int) lo8;
62  }
63
64  /**
65   * Parse a hex string
66   * @param s the hex string
67   */
68  public Unsigned16(String s) throws NumberFormatException {
69    set(s);
70  }
71
72  /**
73   * Set the number from a hex string
74   * @param s the number in hexadecimal
75   * @throws NumberFormatException if the number is invalid
76   */
77  public void set(String s) throws NumberFormatException {
78    hi8 = 0;
79    lo8 = 0;
80    final long lastDigit = 0xfl << 60;
81    for (int i = 0; i < s.length(); ++i) {
82      int digit = getHexDigit(s.charAt(i));
83      if ((lastDigit & hi8) != 0) {
84        throw new NumberFormatException(s + " overflowed 16 bytes");
85      }
86      hi8 <<= 4;
87      hi8 |= (lo8 & lastDigit) >>> 60;
88      lo8 <<= 4;
89      lo8 |= digit;
90    }    
91  }
92
93  /**
94   * Set the number to a given long.
95   * @param l the new value, which is treated as an unsigned number
96   */
97  public void set(long l) {
98    lo8 = l;
99    hi8 = 0;
100  }
101
102  /**
103   * Map a hexadecimal character into a digit.
104   * @param ch the character
105   * @return the digit from 0 to 15
106   * @throws NumberFormatException
107   */
108  private static int getHexDigit(char ch) throws NumberFormatException {
109    if (ch >= '0' && ch <= '9') {
110      return ch - '0';
111    }
112    if (ch >= 'a' && ch <= 'f') {
113      return ch - 'a' + 10;
114    }
115    if (ch >= 'A' && ch <= 'F') {
116      return ch - 'A' + 10;
117    }
118    throw new NumberFormatException(ch + " is not a valid hex digit");
119  }
120
121  private static final Unsigned16 TEN = new Unsigned16(10);
122
123  public static Unsigned16 fromDecimal(String s) throws NumberFormatException {
124    Unsigned16 result = new Unsigned16();
125    Unsigned16 tmp = new Unsigned16();
126    for(int i=0; i < s.length(); i++) {
127      char ch = s.charAt(i);
128      if (ch < '0' || ch > '9') {
129        throw new NumberFormatException(ch + " not a valid decimal digit");
130      }
131      int digit = ch - '0';
132      result.multiply(TEN);
133      tmp.set(digit);
134      result.add(tmp);
135    }
136    return result;
137  }
138
139  /**
140   * Return the number as a hex string.
141   */
142  public String toString() {
143    if (hi8 == 0) {
144      return Long.toHexString(lo8);
145    } else {
146      StringBuilder result = new StringBuilder();
147      result.append(Long.toHexString(hi8));
148      String loString = Long.toHexString(lo8);
149      for(int i=loString.length(); i < 16; ++i) {
150        result.append('0');
151      }
152      result.append(loString);
153      return result.toString();
154    }
155  }
156
157  /**
158   * Get a given byte from the number.
159   * @param b the byte to get with 0 meaning the most significant byte
160   * @return the byte or 0 if b is outside of 0..15
161   */
162  public byte getByte(int b) {
163    if (b >= 0 && b < 16) {
164      if (b < 8) {
165        return (byte) (hi8 >> (56 - 8*b));
166      } else {
167        return (byte) (lo8 >> (120 - 8*b));
168      }
169    }
170    return 0;
171  }
172
173  /**
174   * Get the hexadecimal digit at the given position.
175   * @param p the digit position to get with 0 meaning the most significant
176   * @return the character or '0' if p is outside of 0..31
177   */
178  public char getHexDigit(int p) {
179    byte digit = getByte(p / 2);
180    if (p % 2 == 0) {
181      digit >>>= 4;
182    }
183    digit &= 0xf;
184    if (digit < 10) {
185      return (char) ('0' + digit);
186    } else {
187      return (char) ('A' + digit - 10);
188    }
189  }
190
191  /**
192   * Get the high 8 bytes as a long.
193   */
194  public long getHigh8() {
195    return hi8;
196  }
197  
198  /**
199   * Get the low 8 bytes as a long.
200   */
201  public long getLow8() {
202    return lo8;
203  }
204
205  /**
206   * Multiple the current number by a 16 byte unsigned integer. Overflow is not
207   * detected and the result is the low 16 bytes of the result. The numbers 
208   * are divided into 32 and 31 bit chunks so that the product of two chucks
209   * fits in the unsigned 63 bits of a long.
210   * @param b the other number
211   */
212  void multiply(Unsigned16 b) {
213    // divide the left into 4 32 bit chunks
214    long[] left = new long[4];
215    left[0] = lo8 & 0xffffffffl;
216    left[1] = lo8 >>> 32;
217    left[2] = hi8 & 0xffffffffl;
218    left[3] = hi8 >>> 32;
219    // divide the right into 5 31 bit chunks
220    long[] right = new long[5];
221    right[0] = b.lo8 & 0x7fffffffl;
222    right[1] = (b.lo8 >>> 31) & 0x7fffffffl;
223    right[2] = (b.lo8 >>> 62) + ((b.hi8 & 0x1fffffffl) << 2);
224    right[3] = (b.hi8 >>> 29) & 0x7fffffffl;
225    right[4] = (b.hi8 >>> 60);
226    // clear the cur value
227    set(0);
228    Unsigned16 tmp = new Unsigned16();
229    for(int l=0; l < 4; ++l) {
230      for (int r=0; r < 5; ++r) {
231        long prod = left[l] * right[r];
232        if (prod != 0) {
233          int off = l*32 + r*31;
234          tmp.set(prod);
235          tmp.shiftLeft(off);
236          add(tmp);
237        }
238      }
239    }
240  }
241
242  /**
243   * Add the given number into the current number.
244   * @param b the other number
245   */
246  public void add(Unsigned16 b) {
247    long sumHi;
248    long sumLo;
249    long  reshibit, hibit0, hibit1;
250
251    sumHi = hi8 + b.hi8;
252
253    hibit0 = (lo8 & 0x8000000000000000L);
254    hibit1 = (b.lo8 & 0x8000000000000000L);
255    sumLo = lo8 + b.lo8;
256    reshibit = (sumLo & 0x8000000000000000L);
257    if ((hibit0 & hibit1) != 0 | ((hibit0 ^ hibit1) != 0 && reshibit == 0))
258      sumHi++;  /* add carry bit */
259    hi8 = sumHi;
260    lo8 = sumLo;
261  }
262
263  /**
264   * Shift the number a given number of bit positions. The number is the low
265   * order bits of the result.
266   * @param bits the bit positions to shift by
267   */
268  public void shiftLeft(int bits) {
269    if (bits != 0) {
270      if (bits < 64) {
271        hi8 <<= bits;
272        hi8 |= (lo8 >>> (64 - bits));
273        lo8 <<= bits;
274      } else if (bits < 128) {
275        hi8 = lo8 << (bits - 64);
276        lo8 = 0;
277      } else {
278        hi8 = 0;
279        lo8 = 0;
280      }
281    }
282  }
283  
284  @Override
285  public void readFields(DataInput in) throws IOException {
286    hi8 = in.readLong();
287    lo8 = in.readLong();
288  }
289
290  @Override
291  public void write(DataOutput out) throws IOException {
292    out.writeLong(hi8);
293    out.writeLong(lo8);
294  }
295  
296  
297}