+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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 { 32private long hi8 ; 33private long lo8 ; 34 35public Unsigned16 () { 36hi8 =0 ; 37lo8 =0 ; 38 } 39 40public Unsigned16 (long l ) { 41hi8 =0 ; 42lo8 =l ; 43 } 44 45public Unsigned16 (Unsigned16 other ) { 46hi8 =other .hi8 ; 47lo8 =other .lo8 ; 48 } 49 50@ Override 51public boolean equals (Object o ) { 52if (o instanceof Unsigned16 ) { 53Unsigned16 other = (Unsigned16 )o ; 54return other .hi8 ==hi8 &&other .lo8 ==lo8 ; 55 } 56return false ; 57 } 58 59@ Override 60public int hashCode () { 61return (int )lo8 ; 62 } 63 64/** 65* Parse a hex string 66* @param s the hex string 67*/ 68public Unsigned16 (String s )throws NumberFormatException { 69set (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*/ 77public void set (String s )throws NumberFormatException { 78hi8 =0 ; 79lo8 =0 ; 80final long lastDigit =0xfl <<60 ; 81for (int i =0 ;i <s .length (); ++i ) { 82int digit =getHexDigit (s .charAt (i )); 83if ((lastDigit &hi8 ) !=0 ) { 84throw new NumberFormatException (s +" overflowed 16 bytes" ); 85 } 86hi8 <<=4 ; 87hi8 |= (lo8 &lastDigit ) >>>60 ; 88lo8 <<=4 ; 89lo8 |=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*/ 97public void set (long l ) { 98lo8 =l ; 99hi8 =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*/ 108private static int getHexDigit (char ch )throws NumberFormatException { 109if (ch >='0' &&ch <='9' ) { 110return ch -'0' ; 111 } 112if (ch >='a' &&ch <='f' ) { 113return ch -'a' +10 ; 114 } 115if (ch >='A' &&ch <='F' ) { 116return ch -'A' +10 ; 117 } 118throw new NumberFormatException (ch +" is not a valid hex digit" ); 119 } 120 121private static final Unsigned16 TEN =new Unsigned16 (10 ); 122 123public static Unsigned16 fromDecimal (String s )throws NumberFormatException { 124Unsigned16 result =new Unsigned16 (); 125Unsigned16 tmp =new Unsigned16 (); 126for (int i =0 ;i <s .length ();i ++) { 127char ch =s .charAt (i ); 128if (ch <'0' ||ch >'9' ) { 129throw new NumberFormatException (ch +" not a valid decimal digit" ); 130 } 131int digit =ch -'0' ; 132result .multiply (TEN ); 133tmp .set (digit ); 134result .add (tmp ); 135 } 136return result ; 137 } 138 139/** 140* Return the number as a hex string. 141*/ 142public String toString () { 143if (hi8 ==0 ) { 144return Long .toHexString (lo8 ); 145 }else { 146StringBuilder result =new StringBuilder (); 147result .append (Long .toHexString (hi8 )); 148String loString =Long .toHexString (lo8 ); 149for (int i =loString .length ();i <16 ; ++i ) { 150result .append ('0' ); 151 } 152result .append (loString ); 153return 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*/ 162public byte getByte (int b ) { 163if (b >=0 &&b <16 ) { 164if (b <8 ) { 165return (byte ) (hi8 >> (56 -8 *b )); 166 }else { 167return (byte ) (lo8 >> (120 -8 *b )); 168 } 169 } 170return 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*/ 178public char getHexDigit (int p ) { 179byte digit =getByte (p /2 ); 180if (p %2 ==0 ) { 181digit >>>=4 ; 182 } 183digit &=0xf ; 184if (digit <10 ) { 185return (char ) ('0' +digit ); 186 }else { 187return (char ) ('A' +digit -10 ); 188 } 189 } 190 191/** 192* Get the high 8 bytes as a long. 193*/ 194public long getHigh8 () { 195return hi8 ; 196 } 197 198/** 199* Get the low 8 bytes as a long. 200*/ 201public long getLow8 () { 202return 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*/ 212void multiply (Unsigned16 b ) { 213// divide the left into 4 32 bit chunks 214long []left =new long [4 ]; 215left [0 ] =lo8 &0xffffffffl ; 216left [1 ] =lo8 >>>32 ; 217left [2 ] =hi8 &0xffffffffl ; 218left [3 ] =hi8 >>>32 ; 219// divide the right into 5 31 bit chunks 220long []right =new long [5 ]; 221right [0 ] =b .lo8 &0x7fffffffl ; 222right [1 ] = (b .lo8 >>>31 ) &0x7fffffffl ; 223right [2 ] = (b .lo8 >>>62 ) + ((b .hi8 &0x1fffffffl ) <<2 ); 224right [3 ] = (b .hi8 >>>29 ) &0x7fffffffl ; 225right [4 ] = (b .hi8 >>>60 ); 226// clear the cur value 227set (0 ); 228Unsigned16 tmp =new Unsigned16 (); 229for (int l =0 ;l <4 ; ++l ) { 230for (int r =0 ;r <5 ; ++r ) { 231long prod =left [l ] *right [r ]; 232if (prod !=0 ) { 233int off =l *32 +r *31 ; 234tmp .set (prod ); 235tmp .shiftLeft (off ); 236add (tmp ); 237 } 238 } 239 } 240 } 241 242/** 243* Add the given number into the current number. 244* @param b the other number 245*/ 246public void add (Unsigned16 b ) { 247long sumHi ; 248long sumLo ; 249long reshibit ,hibit0 ,hibit1 ; 250 251sumHi =hi8 +b .hi8 ; 252 253hibit0 = (lo8 &0x8000000000000000L ); 254hibit1 = (b .lo8 &0x8000000000000000L ); 255sumLo =lo8 +b .lo8 ; 256reshibit = (sumLo &0x8000000000000000L ); 257if ((hibit0 &hibit1 ) !=0 | ((hibit0 ^hibit1 ) !=0 &&reshibit ==0 )) 258sumHi ++;/* add carry bit */ 259hi8 =sumHi ; 260lo8 =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*/ 268public void shiftLeft (int bits ) { 269if (bits !=0 ) { 270if (bits <64 ) { 271hi8 <<=bits ; 272hi8 |= (lo8 >>> (64 -bits )); 273lo8 <<=bits ; 274 }else if (bits <128 ) { 275hi8 =lo8 << (bits -64 ); 276lo8 =0 ; 277 }else { 278hi8 =0 ; 279lo8 =0 ; 280 } 281 } 282 } 283 284@ Override 285public void readFields (DataInput in )throws IOException { 286hi8 =in .readLong (); 287lo8 =in .readLong (); 288 } 289 290@ Override 291public void write (DataOutput out )throws IOException { 292out .writeLong (hi8 ); 293out .writeLong (lo8 ); 294 } 295 296 297}