| /** |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package org.apache.hadoop.examples.terasort; |
| |
| import java.io.DataInput; |
| import java.io.DataOutput; |
| import java.io.IOException; |
| |
| import org.apache.hadoop.io.Writable; |
| |
| /** |
| * An unsigned 16 byte integer class that supports addition, multiplication, |
| * and left shifts. |
| */ |
| class Unsigned16 implements Writable { |
| private long hi8; |
| private long lo8; |
| |
| public Unsigned16() { |
| hi8 = 0; |
| lo8 = 0; |
| } |
| |
| public Unsigned16(long l) { |
| hi8 = 0; |
| lo8 = l; |
| } |
| |
| public Unsigned16(Unsigned16 other) { |
| hi8 = other.hi8; |
| lo8 = other.lo8; |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (o instanceof Unsigned16) { |
| Unsigned16 other = (Unsigned16) o; |
| return other.hi8 == hi8 && other.lo8 == lo8; |
| } |
| return false; |
| } |
| |
| @Override |
| public int hashCode() { |
| return (int) lo8; |
| } |
| |
| /** |
| * Parse a hex string |
| * @param s the hex string |
| */ |
| public Unsigned16(String s) throws NumberFormatException { |
| set(s); |
| } |
| |
| /** |
| * Set the number from a hex string |
| * @param s the number in hexadecimal |
| * @throws NumberFormatException if the number is invalid |
| */ |
| public void set(String s) throws NumberFormatException { |
| hi8 = 0; |
| lo8 = 0; |
| final long lastDigit = 0xfl << 60; |
| for (int i = 0; i < s.length(); ++i) { |
| int digit = getHexDigit(s.charAt(i)); |
| if ((lastDigit & hi8) != 0) { |
| throw new NumberFormatException(s + " overflowed 16 bytes"); |
| } |
| hi8 <<= 4; |
| hi8 |= (lo8 & lastDigit) >>> 60; |
| lo8 <<= 4; |
| lo8 |= digit; |
| } |
| } |
| |
| /** |
| * Set the number to a given long. |
| * @param l the new value, which is treated as an unsigned number |
| */ |
| public void set(long l) { |
| lo8 = l; |
| hi8 = 0; |
| } |
| |
| /** |
| * Map a hexadecimal character into a digit. |
| * @param ch the character |
| * @return the digit from 0 to 15 |
| * @throws NumberFormatException |
| */ |
| private static int getHexDigit(char ch) throws NumberFormatException { |
| if (ch >= '0' && ch <= '9') { |
| return ch - '0'; |
| } |
| if (ch >= 'a' && ch <= 'f') { |
| return ch - 'a' + 10; |
| } |
| if (ch >= 'A' && ch <= 'F') { |
| return ch - 'A' + 10; |
| } |
| throw new NumberFormatException(ch + " is not a valid hex digit"); |
| } |
| |
| private static final Unsigned16 TEN = new Unsigned16(10); |
| |
| public static Unsigned16 fromDecimal(String s) throws NumberFormatException { |
| Unsigned16 result = new Unsigned16(); |
| Unsigned16 tmp = new Unsigned16(); |
| for(int i=0; i < s.length(); i++) { |
| char ch = s.charAt(i); |
| if (ch < '0' || ch > '9') { |
| throw new NumberFormatException(ch + " not a valid decimal digit"); |
| } |
| int digit = ch - '0'; |
| result.multiply(TEN); |
| tmp.set(digit); |
| result.add(tmp); |
| } |
| return result; |
| } |
| |
| /** |
| * Return the number as a hex string. |
| */ |
| public String toString() { |
| if (hi8 == 0) { |
| return Long.toHexString(lo8); |
| } else { |
| StringBuilder result = new StringBuilder(); |
| result.append(Long.toHexString(hi8)); |
| String loString = Long.toHexString(lo8); |
| for(int i=loString.length(); i < 16; ++i) { |
| result.append('0'); |
| } |
| result.append(loString); |
| return result.toString(); |
| } |
| } |
| |
| /** |
| * Get a given byte from the number. |
| * @param b the byte to get with 0 meaning the most significant byte |
| * @return the byte or 0 if b is outside of 0..15 |
| */ |
| public byte getByte(int b) { |
| if (b >= 0 && b < 16) { |
| if (b < 8) { |
| return (byte) (hi8 >> (56 - 8*b)); |
| } else { |
| return (byte) (lo8 >> (120 - 8*b)); |
| } |
| } |
| return 0; |
| } |
| |
| /** |
| * Get the hexadecimal digit at the given position. |
| * @param p the digit position to get with 0 meaning the most significant |
| * @return the character or '0' if p is outside of 0..31 |
| */ |
| public char getHexDigit(int p) { |
| byte digit = getByte(p / 2); |
| if (p % 2 == 0) { |
| digit >>>= 4; |
| } |
| digit &= 0xf; |
| if (digit < 10) { |
| return (char) ('0' + digit); |
| } else { |
| return (char) ('A' + digit - 10); |
| } |
| } |
| |
| /** |
| * Get the high 8 bytes as a long. |
| */ |
| public long getHigh8() { |
| return hi8; |
| } |
| |
| /** |
| * Get the low 8 bytes as a long. |
| */ |
| public long getLow8() { |
| return lo8; |
| } |
| |
| /** |
| * Multiple the current number by a 16 byte unsigned integer. Overflow is not |
| * detected and the result is the low 16 bytes of the result. The numbers |
| * are divided into 32 and 31 bit chunks so that the product of two chucks |
| * fits in the unsigned 63 bits of a long. |
| * @param b the other number |
| */ |
| void multiply(Unsigned16 b) { |
| // divide the left into 4 32 bit chunks |
| long[] left = new long[4]; |
| left[0] = lo8 & 0xffffffffl; |
| left[1] = lo8 >>> 32; |
| left[2] = hi8 & 0xffffffffl; |
| left[3] = hi8 >>> 32; |
| // divide the right into 5 31 bit chunks |
| long[] right = new long[5]; |
| right[0] = b.lo8 & 0x7fffffffl; |
| right[1] = (b.lo8 >>> 31) & 0x7fffffffl; |
| right[2] = (b.lo8 >>> 62) + ((b.hi8 & 0x1fffffffl) << 2); |
| right[3] = (b.hi8 >>> 29) & 0x7fffffffl; |
| right[4] = (b.hi8 >>> 60); |
| // clear the cur value |
| set(0); |
| Unsigned16 tmp = new Unsigned16(); |
| for(int l=0; l < 4; ++l) { |
| for (int r=0; r < 5; ++r) { |
| long prod = left[l] * right[r]; |
| if (prod != 0) { |
| int off = l*32 + r*31; |
| tmp.set(prod); |
| tmp.shiftLeft(off); |
| add(tmp); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Add the given number into the current number. |
| * @param b the other number |
| */ |
| public void add(Unsigned16 b) { |
| long sumHi; |
| long sumLo; |
| long reshibit, hibit0, hibit1; |
| |
| sumHi = hi8 + b.hi8; |
| |
| hibit0 = (lo8 & 0x8000000000000000L); |
| hibit1 = (b.lo8 & 0x8000000000000000L); |
| sumLo = lo8 + b.lo8; |
| reshibit = (sumLo & 0x8000000000000000L); |
| if ((hibit0 & hibit1) != 0 | ((hibit0 ^ hibit1) != 0 && reshibit == 0)) |
| sumHi++; /* add carry bit */ |
| hi8 = sumHi; |
| lo8 = sumLo; |
| } |
| |
| /** |
| * Shift the number a given number of bit positions. The number is the low |
| * order bits of the result. |
| * @param bits the bit positions to shift by |
| */ |
| public void shiftLeft(int bits) { |
| if (bits != 0) { |
| if (bits < 64) { |
| hi8 <<= bits; |
| hi8 |= (lo8 >>> (64 - bits)); |
| lo8 <<= bits; |
| } else if (bits < 128) { |
| hi8 = lo8 << (bits - 64); |
| lo8 = 0; |
| } else { |
| hi8 = 0; |
| lo8 = 0; |
| } |
| } |
| } |
| |
| @Override |
| public void readFields(DataInput in) throws IOException { |
| hi8 = in.readLong(); |
| lo8 = in.readLong(); |
| } |
| |
| @Override |
| public void write(DataOutput out) throws IOException { |
| out.writeLong(hi8); |
| out.writeLong(lo8); |
| } |
| |
| |
| } |