001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.util;
019
020import static org.junit.Assert.assertArrayEquals;
021import static org.junit.Assert.assertEquals;
022import static org.junit.Assert.assertTrue;
023import static org.junit.Assert.fail;
024
025import java.math.BigDecimal;
026import java.util.Arrays;
027import java.util.Collections;
028import java.util.concurrent.ThreadLocalRandom;
029import org.apache.hadoop.hbase.HBaseClassTestRule;
030import org.apache.hadoop.hbase.testclassification.MiscTests;
031import org.apache.hadoop.hbase.testclassification.SmallTests;
032import org.junit.ClassRule;
033import org.junit.Test;
034import org.junit.experimental.categories.Category;
035
036@Category({ MiscTests.class, SmallTests.class })
037public class TestOrderedBytes {
038
039  @ClassRule
040  public static final HBaseClassTestRule CLASS_RULE =
041    HBaseClassTestRule.forClass(TestOrderedBytes.class);
042
043  // integer constants for testing Numeric code paths
044  static final Long[] I_VALS =
045    { 0L, 1L, 10L, 99L, 100L, 1234L, 9999L, 10000L, 10001L, 12345L, 123450L, Long.MAX_VALUE, -1L,
046      -10L, -99L, -100L, -123L, -999L, -10000L, -10001L, -12345L, -123450L, Long.MIN_VALUE };
047  static final int[] I_LENGTHS =
048    { 1, 2, 2, 2, 2, 3, 3, 2, 4, 4, 4, 11, 2, 2, 2, 2, 3, 3, 2, 4, 4, 4, 11 };
049
050  // real constants for testing Numeric code paths
051  static final Double[] D_VALS =
052    { 0.0, 0.00123, 0.0123, 0.123, 1.0, 10.0, 12.345, 99.0, 99.01, 99.0001, 100.0, 100.01, 100.1,
053      1234.0, 1234.5, 9999.0, 9999.000001, 9999.000009, 9999.00001, 9999.00009, 9999.000099,
054      9999.0001, 9999.001, 9999.01, 9999.1, 10000.0, 10001.0, 12345.0, 123450.0,
055      Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, Double.NaN, Double.MAX_VALUE, -0.00123,
056      -0.0123, -0.123, -1.0, -10.0, -12.345, -99.0, -99.01, -99.0001, -100.0, -100.01, -100.1,
057      -1234.0, -1234.5, -9999.0, -9999.000001, -9999.000009, -9999.00001, -9999.00009, -9999.000099,
058      -9999.0001, -9999.001, -9999.01, -9999.1, -10000.0, -10001.0, -12345.0, -123450.0 };
059  static final int[] D_LENGTHS =
060    { 1, 4, 4, 4, 2, 2, 4, 2, 3, 4, 2, 4, 4, 3, 4, 3, 6, 6, 6, 6, 6, 5, 5, 4, 4, 2, 4, 4, 4, 1, 1,
061      1, 11, 4, 4, 4, 2, 2, 4, 2, 3, 4, 2, 4, 4, 3, 4, 3, 6, 6, 6, 6, 6, 5, 5, 4, 4, 2, 4, 4, 4 };
062
063  // fill in other gaps in Numeric code paths
064  static final BigDecimal[] BD_VALS = { null, BigDecimal.valueOf(Long.MAX_VALUE),
065    BigDecimal.valueOf(Long.MIN_VALUE), BigDecimal.valueOf(Double.MAX_VALUE),
066    BigDecimal.valueOf(Double.MIN_VALUE),
067    BigDecimal.valueOf(Long.MAX_VALUE).multiply(BigDecimal.valueOf(100)),
068    BigDecimal.valueOf(Long.MAX_VALUE).pow(64), BigDecimal.valueOf(Long.MAX_VALUE).pow(64).negate(),
069    new BigDecimal("0." + String.join("", Collections.nCopies(500, "123"))),
070    new BigDecimal("-0." + String.join("", Collections.nCopies(500, "123"))) };
071  static final int[] BD_LENGTHS = { 1, 11, 11, 11, 4, 12, 19, 19, 18, 18 };
072
073  /*
074   * This is the smallest difference between two doubles in D_VALS
075   */
076  static final double MIN_EPSILON = 0.000001;
077
078  /**
079   * Expected lengths of equivalent values should match
080   */
081  @Test
082  public void testVerifyTestIntegrity() {
083    for (int i = 0; i < I_VALS.length; i++) {
084      for (int d = 0; d < D_VALS.length; d++) {
085        if (Math.abs(I_VALS[i] - D_VALS[d]) < MIN_EPSILON) {
086          assertEquals(
087            "Test inconsistency detected: expected lengths for " + I_VALS[i] + " do not match.",
088            I_LENGTHS[i], D_LENGTHS[d]);
089        }
090      }
091    }
092  }
093
094  /**
095   * Tests the variable uint64 encoding.
096   * <p>
097   * Building sqlite4 with -DVARINT_TOOL provides this reference:<br />
098   * <code>$ ./varint_tool 240 2287 67823 16777215 4294967295 1099511627775
099   *   281474976710655 72057594037927935 18446744073709551615<br />
100   * 240 = f0<br />
101   * 2287 = f8ff<br />
102   * 67823 = f9ffff<br />
103   * 16777215 = faffffff<br />
104   * 4294967295 = fbffffffff<br />
105   * 1099511627775 = fcffffffffff<br />
106   * 281474976710655 = fdffffffffffff<br />
107   * 72057594037927935 = feffffffffffffff<br />
108   * 9223372036854775807 = ff7fffffffffffffff (Long.MAX_VAL)<br />
109   * 9223372036854775808 = ff8000000000000000 (Long.MIN_VAL)<br />
110   * 18446744073709551615 = ffffffffffffffffff<br /></code>
111   * </p>
112   */
113  @Test
114  public void testVaruint64Boundaries() {
115    long[] vals = { 239L, 240L, 2286L, 2287L, 67822L, 67823L, 16777214L, 16777215L, 4294967294L,
116      4294967295L, 1099511627774L, 1099511627775L, 281474976710654L, 281474976710655L,
117      72057594037927934L, 72057594037927935L, Long.MAX_VALUE - 1, Long.MAX_VALUE,
118      Long.MIN_VALUE + 1, Long.MIN_VALUE, -2L, -1L };
119    int[] lens = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9 };
120    assertEquals("Broken test!", vals.length, lens.length);
121
122    /*
123     * assert encoded values match decoded values. encode into target buffer starting at an offset
124     * to detect over/underflow conditions.
125     */
126    for (boolean comp : new boolean[] { true, false }) {
127      for (int i = 0; i < vals.length; i++) {
128        // allocate a buffer 2-bytes larger than necessary and place our range over the center.
129        byte[] a = new byte[lens[i] + 2];
130        PositionedByteRange buf = new SimplePositionedMutableByteRange(a, 1, lens[i]);
131
132        // verify encode
133        assertEquals("Surprising return value.", lens[i],
134          OrderedBytes.putVaruint64(buf, vals[i], comp));
135        assertEquals("Surprising serialized length.", lens[i], buf.getPosition());
136        assertEquals("Buffer underflow.", 0, a[0]);
137        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
138
139        // verify skip
140        buf.setPosition(0);
141        assertEquals("Surprising return value.", lens[i], OrderedBytes.skipVaruint64(buf, comp));
142        assertEquals("Did not skip enough bytes.", lens[i], buf.getPosition());
143
144        // verify decode
145        buf.setPosition(0);
146        assertEquals("Deserialization failed.", vals[i], OrderedBytes.getVaruint64(buf, comp));
147        assertEquals("Did not consume enough bytes.", lens[i], buf.getPosition());
148      }
149    }
150  }
151
152  /**
153   * Test integer encoding. Example input values come from reference wiki page.
154   */
155  @Test
156  public void testNumericInt() {
157    /*
158     * assert encoded values match decoded values. encode into target buffer starting at an offset
159     * to detect over/underflow conditions.
160     */
161    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
162      for (int i = 0; i < I_VALS.length; i++) {
163        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
164        byte[] a = new byte[I_LENGTHS[i] + 3];
165        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, I_LENGTHS[i] + 1);
166        buf1.setPosition(1);
167
168        // verify encode
169        assertEquals("Surprising return value.", I_LENGTHS[i],
170          OrderedBytes.encodeNumeric(buf1, I_VALS[i], ord));
171        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
172          buf1.getPosition());
173        assertEquals("Surprising serialized length.", I_LENGTHS[i], buf1.getPosition() - 1);
174        assertEquals("Buffer underflow.", 0, a[0]);
175        assertEquals("Buffer underflow.", 0, a[1]);
176        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
177
178        // verify skip
179        buf1.setPosition(1);
180        assertEquals("Surprising return value.", I_LENGTHS[i], OrderedBytes.skip(buf1));
181        assertEquals("Did not skip enough bytes.", I_LENGTHS[i], buf1.getPosition() - 1);
182
183        // verify decode
184        buf1.setPosition(1);
185        assertEquals("Deserialization failed.", I_VALS[i].longValue(),
186          OrderedBytes.decodeNumericAsLong(buf1));
187        assertEquals("Did not consume enough bytes.", I_LENGTHS[i], buf1.getPosition() - 1);
188      }
189    }
190
191    /*
192     * assert natural sort order is preserved by the codec.
193     */
194    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
195      byte[][] encoded = new byte[I_VALS.length][];
196      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
197      for (int i = 0; i < I_VALS.length; i++) {
198        encoded[i] = new byte[I_LENGTHS[i]];
199        OrderedBytes.encodeNumeric(pbr.set(encoded[i]), I_VALS[i], ord);
200      }
201
202      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
203      Long[] sortedVals = Arrays.copyOf(I_VALS, I_VALS.length);
204
205      if (ord == Order.ASCENDING) {
206        Arrays.sort(sortedVals);
207      } else {
208        Arrays.sort(sortedVals, Collections.reverseOrder());
209      }
210
211      for (int i = 0; i < sortedVals.length; i++) {
212        pbr.set(encoded[i]);
213        long decoded = OrderedBytes.decodeNumericAsLong(pbr);
214        assertEquals(
215          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
216            sortedVals[i], decoded, ord),
217          sortedVals[i].longValue(), decoded);
218      }
219    }
220  }
221
222  /**
223   * Test real encoding. Example input values come from reference wiki page.
224   */
225  @Test
226  public void testNumericReal() {
227    /*
228     * assert encoded values match decoded values. encode into target buffer starting at an offset
229     * to detect over/underflow conditions.
230     */
231    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
232      for (int i = 0; i < D_VALS.length; i++) {
233        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
234        byte[] a = new byte[D_LENGTHS[i] + 3];
235        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, D_LENGTHS[i] + 1);
236        buf1.setPosition(1);
237
238        // verify encode
239        assertEquals("Surprising return value.", D_LENGTHS[i],
240          OrderedBytes.encodeNumeric(buf1, D_VALS[i], ord));
241        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
242          buf1.getPosition());
243        assertEquals("Surprising serialized length.", D_LENGTHS[i], buf1.getPosition() - 1);
244        assertEquals("Buffer underflow.", 0, a[0]);
245        assertEquals("Buffer underflow.", 0, a[1]);
246        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
247
248        // verify skip
249        buf1.setPosition(1);
250        assertEquals("Surprising return value.", D_LENGTHS[i], OrderedBytes.skip(buf1));
251        assertEquals("Did not skip enough bytes.", D_LENGTHS[i], buf1.getPosition() - 1);
252
253        // verify decode
254        buf1.setPosition(1);
255        assertEquals("Deserialization failed.", D_VALS[i], OrderedBytes.decodeNumericAsDouble(buf1),
256          MIN_EPSILON);
257        assertEquals("Did not consume enough bytes.", D_LENGTHS[i], buf1.getPosition() - 1);
258      }
259    }
260
261    /*
262     * assert natural sort order is preserved by the codec.
263     */
264    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
265      byte[][] encoded = new byte[D_VALS.length][];
266      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
267      for (int i = 0; i < D_VALS.length; i++) {
268        encoded[i] = new byte[D_LENGTHS[i]];
269        OrderedBytes.encodeNumeric(pbr.set(encoded[i]), D_VALS[i], ord);
270      }
271
272      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
273      Double[] sortedVals = Arrays.copyOf(D_VALS, D_VALS.length);
274
275      if (ord == Order.ASCENDING) {
276        Arrays.sort(sortedVals);
277      } else {
278        Arrays.sort(sortedVals, Collections.reverseOrder());
279      }
280
281      for (int i = 0; i < sortedVals.length; i++) {
282        pbr.set(encoded[i]);
283        double decoded = OrderedBytes.decodeNumericAsDouble(pbr);
284        assertEquals(
285          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
286            sortedVals[i], decoded, ord),
287          sortedVals[i], decoded, MIN_EPSILON);
288      }
289    }
290  }
291
292  /**
293   * Fill gaps in Numeric encoding testing.
294   */
295  @Test
296  public void testNumericOther() {
297    /*
298     * assert encoded values match decoded values. encode into target buffer starting at an offset
299     * to detect over/underflow conditions.
300     */
301    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
302      for (int i = 0; i < BD_VALS.length; i++) {
303        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
304        byte[] a = new byte[BD_LENGTHS[i] + 3];
305        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, BD_LENGTHS[i] + 1);
306        buf1.setPosition(1);
307
308        // verify encode
309        assertEquals("Surprising return value.", BD_LENGTHS[i],
310          OrderedBytes.encodeNumeric(buf1, BD_VALS[i], ord));
311        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
312          buf1.getPosition());
313        assertEquals("Surprising serialized length.", BD_LENGTHS[i], buf1.getPosition() - 1);
314        assertEquals("Buffer underflow.", 0, a[0]);
315        assertEquals("Buffer underflow.", 0, a[1]);
316        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
317
318        // verify skip
319        buf1.setPosition(1);
320        assertEquals("Surprising return value.", BD_LENGTHS[i], OrderedBytes.skip(buf1));
321        assertEquals("Did not skip enough bytes.", BD_LENGTHS[i], buf1.getPosition() - 1);
322
323        // verify decode
324        buf1.setPosition(1);
325        BigDecimal decoded = OrderedBytes.decodeNumericAsBigDecimal(buf1);
326        if (null == BD_VALS[i]) {
327          assertEquals(BD_VALS[i], decoded);
328        } else {
329          // The num will be rounded to a specific precision in the encoding phase.
330          // So that big value will lose precision here. Need to add a normalization here to
331          // make the test pass.
332          assertEquals("Deserialization failed.", 0,
333            OrderedBytes.normalize(BD_VALS[i]).compareTo(decoded));
334        }
335        assertEquals("Did not consume enough bytes.", BD_LENGTHS[i], buf1.getPosition() - 1);
336      }
337    }
338  }
339
340  /**
341   * Verify Real and Int encodings are compatible.
342   */
343  @Test
344  public void testNumericIntRealCompatibility() {
345    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
346      for (int i = 0; i < I_VALS.length; i++) {
347        // verify primitives
348        PositionedByteRange pbri = new SimplePositionedMutableByteRange(I_LENGTHS[i]);
349        PositionedByteRange pbrr = new SimplePositionedMutableByteRange(I_LENGTHS[i]);
350        OrderedBytes.encodeNumeric(pbri, I_VALS[i], ord);
351        OrderedBytes.encodeNumeric(pbrr, I_VALS[i], ord);
352        assertArrayEquals("Integer and real encodings differ.", pbri.getBytes(), pbrr.getBytes());
353        pbri.setPosition(0);
354        pbrr.setPosition(0);
355        assertEquals((long) I_VALS[i], OrderedBytes.decodeNumericAsLong(pbri));
356        assertEquals((long) I_VALS[i], (long) OrderedBytes.decodeNumericAsDouble(pbrr));
357
358        // verify BigDecimal for Real encoding
359        BigDecimal bd = BigDecimal.valueOf(I_VALS[i]);
360        PositionedByteRange pbrbd = new SimplePositionedMutableByteRange(I_LENGTHS[i]);
361        OrderedBytes.encodeNumeric(pbrbd, bd, ord);
362        assertArrayEquals("Integer and BigDecimal encodings differ.", pbri.getBytes(),
363          pbrbd.getBytes());
364        pbri.setPosition(0);
365        assertEquals("Value not preserved when decoding as Long", 0,
366          bd.compareTo(BigDecimal.valueOf(OrderedBytes.decodeNumericAsLong(pbri))));
367      }
368    }
369  }
370
371  /**
372   * Test int8 encoding.
373   */
374  @Test
375  public void testInt8() {
376    Byte[] vals = { Byte.MIN_VALUE, Byte.MIN_VALUE / 2, 0, Byte.MAX_VALUE / 2, Byte.MAX_VALUE };
377
378    /*
379     * assert encoded values match decoded values. encode into target buffer starting at an offset
380     * to detect over/underflow conditions.
381     */
382    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
383      for (Byte val : vals) {
384        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
385        byte[] a = new byte[2 + 3];
386        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, 2 + 1);
387        buf1.setPosition(1);
388
389        // verify encode
390        assertEquals("Surprising return value.", 2, OrderedBytes.encodeInt8(buf1, val, ord));
391        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
392          buf1.getPosition());
393        assertEquals("Surprising serialized length.", 2, buf1.getPosition() - 1);
394        assertEquals("Buffer underflow.", 0, a[0]);
395        assertEquals("Buffer underflow.", 0, a[1]);
396        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
397
398        // verify skip
399        buf1.setPosition(1);
400        assertEquals("Surprising return value.", 2, OrderedBytes.skip(buf1));
401        assertEquals("Did not skip enough bytes.", 2, buf1.getPosition() - 1);
402
403        // verify decode
404        buf1.setPosition(1);
405        assertEquals("Deserialization failed.", val.byteValue(), OrderedBytes.decodeInt8(buf1));
406        assertEquals("Did not consume enough bytes.", 2, buf1.getPosition() - 1);
407      }
408    }
409
410    /*
411     * assert natural sort order is preserved by the codec.
412     */
413    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
414      byte[][] encoded = new byte[vals.length][2];
415      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
416      for (int i = 0; i < vals.length; i++) {
417        OrderedBytes.encodeInt8(pbr.set(encoded[i]), vals[i], ord);
418      }
419
420      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
421      Byte[] sortedVals = Arrays.copyOf(vals, vals.length);
422
423      if (ord == Order.ASCENDING) {
424        Arrays.sort(sortedVals);
425      } else {
426        Arrays.sort(sortedVals, Collections.reverseOrder());
427      }
428
429      for (int i = 0; i < sortedVals.length; i++) {
430        int decoded = OrderedBytes.decodeInt8(pbr.set(encoded[i]));
431        assertEquals(
432          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
433            sortedVals[i], decoded, ord),
434          sortedVals[i].byteValue(), decoded);
435      }
436    }
437  }
438
439  /**
440   * Test int16 encoding.
441   */
442  @Test
443  public void testInt16() {
444    Short[] vals =
445      { Short.MIN_VALUE, Short.MIN_VALUE / 2, 0, Short.MAX_VALUE / 2, Short.MAX_VALUE };
446
447    /*
448     * assert encoded values match decoded values. encode into target buffer starting at an offset
449     * to detect over/underflow conditions.
450     */
451    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
452      for (Short val : vals) {
453        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
454        byte[] a = new byte[3 + 3];
455        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, 3 + 1);
456        buf1.setPosition(1);
457
458        // verify encode
459        assertEquals("Surprising return value.", 3, OrderedBytes.encodeInt16(buf1, val, ord));
460        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
461          buf1.getPosition());
462        assertEquals("Surprising serialized length.", 3, buf1.getPosition() - 1);
463        assertEquals("Buffer underflow.", 0, a[0]);
464        assertEquals("Buffer underflow.", 0, a[1]);
465        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
466
467        // verify skip
468        buf1.setPosition(1);
469        assertEquals("Surprising return value.", 3, OrderedBytes.skip(buf1));
470        assertEquals("Did not skip enough bytes.", 3, buf1.getPosition() - 1);
471
472        // verify decode
473        buf1.setPosition(1);
474        assertEquals("Deserialization failed.", val.shortValue(), OrderedBytes.decodeInt16(buf1));
475        assertEquals("Did not consume enough bytes.", 3, buf1.getPosition() - 1);
476      }
477    }
478
479    /*
480     * assert natural sort order is preserved by the codec.
481     */
482    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
483      byte[][] encoded = new byte[vals.length][3];
484      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
485      for (int i = 0; i < vals.length; i++) {
486        OrderedBytes.encodeInt16(pbr.set(encoded[i]), vals[i], ord);
487      }
488
489      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
490      Short[] sortedVals = Arrays.copyOf(vals, vals.length);
491
492      if (ord == Order.ASCENDING) {
493        Arrays.sort(sortedVals);
494      } else {
495        Arrays.sort(sortedVals, Collections.reverseOrder());
496      }
497
498      for (int i = 0; i < sortedVals.length; i++) {
499        int decoded = OrderedBytes.decodeInt16(pbr.set(encoded[i]));
500        assertEquals(
501          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
502            sortedVals[i], decoded, ord),
503          sortedVals[i].shortValue(), decoded);
504      }
505    }
506  }
507
508  /**
509   * Test int32 encoding.
510   */
511  @Test
512  public void testInt32() {
513    Integer[] vals =
514      { Integer.MIN_VALUE, Integer.MIN_VALUE / 2, 0, Integer.MAX_VALUE / 2, Integer.MAX_VALUE };
515
516    /*
517     * assert encoded values match decoded values. encode into target buffer starting at an offset
518     * to detect over/underflow conditions.
519     */
520    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
521      for (Integer val : vals) {
522        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
523        byte[] a = new byte[5 + 3];
524        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, 5 + 1);
525        buf1.setPosition(1);
526
527        // verify encode
528        assertEquals("Surprising return value.", 5, OrderedBytes.encodeInt32(buf1, val, ord));
529        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
530          buf1.getPosition());
531        assertEquals("Surprising serialized length.", 5, buf1.getPosition() - 1);
532        assertEquals("Buffer underflow.", 0, a[0]);
533        assertEquals("Buffer underflow.", 0, a[1]);
534        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
535
536        // verify skip
537        buf1.setPosition(1);
538        assertEquals("Surprising return value.", 5, OrderedBytes.skip(buf1));
539        assertEquals("Did not skip enough bytes.", 5, buf1.getPosition() - 1);
540
541        // verify decode
542        buf1.setPosition(1);
543        assertEquals("Deserialization failed.", val.intValue(), OrderedBytes.decodeInt32(buf1));
544        assertEquals("Did not consume enough bytes.", 5, buf1.getPosition() - 1);
545      }
546    }
547
548    /*
549     * assert natural sort order is preserved by the codec.
550     */
551    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
552      byte[][] encoded = new byte[vals.length][5];
553      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
554      for (int i = 0; i < vals.length; i++) {
555        OrderedBytes.encodeInt32(pbr.set(encoded[i]), vals[i], ord);
556      }
557
558      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
559      Integer[] sortedVals = Arrays.copyOf(vals, vals.length);
560
561      if (ord == Order.ASCENDING) {
562        Arrays.sort(sortedVals);
563      } else {
564        Arrays.sort(sortedVals, Collections.reverseOrder());
565      }
566
567      for (int i = 0; i < sortedVals.length; i++) {
568        int decoded = OrderedBytes.decodeInt32(pbr.set(encoded[i]));
569        assertEquals(
570          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
571            sortedVals[i], decoded, ord),
572          sortedVals[i].intValue(), decoded);
573      }
574    }
575  }
576
577  /**
578   * Test int64 encoding.
579   */
580  @Test
581  public void testInt64() {
582    Long[] vals = { Long.MIN_VALUE, Long.MIN_VALUE / 2, 0L, Long.MAX_VALUE / 2, Long.MAX_VALUE };
583
584    /*
585     * assert encoded values match decoded values. encode into target buffer starting at an offset
586     * to detect over/underflow conditions.
587     */
588    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
589      for (Long val : vals) {
590        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
591        byte[] a = new byte[9 + 3];
592        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, 9 + 1);
593        buf1.setPosition(1);
594
595        // verify encode
596        assertEquals("Surprising return value.", 9, OrderedBytes.encodeInt64(buf1, val, ord));
597        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
598          buf1.getPosition());
599        assertEquals("Surprising serialized length.", 9, buf1.getPosition() - 1);
600        assertEquals("Buffer underflow.", 0, a[0]);
601        assertEquals("Buffer underflow.", 0, a[1]);
602        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
603
604        // verify skip
605        buf1.setPosition(1);
606        assertEquals("Surprising return value.", 9, OrderedBytes.skip(buf1));
607        assertEquals("Did not skip enough bytes.", 9, buf1.getPosition() - 1);
608
609        // verify decode
610        buf1.setPosition(1);
611        assertEquals("Deserialization failed.", val.longValue(), OrderedBytes.decodeInt64(buf1));
612        assertEquals("Did not consume enough bytes.", 9, buf1.getPosition() - 1);
613      }
614    }
615
616    /*
617     * assert natural sort order is preserved by the codec.
618     */
619    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
620      byte[][] encoded = new byte[vals.length][9];
621      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
622      for (int i = 0; i < vals.length; i++) {
623        OrderedBytes.encodeInt64(pbr.set(encoded[i]), vals[i], ord);
624      }
625
626      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
627      Long[] sortedVals = Arrays.copyOf(vals, vals.length);
628
629      if (ord == Order.ASCENDING) {
630        Arrays.sort(sortedVals);
631      } else {
632        Arrays.sort(sortedVals, Collections.reverseOrder());
633      }
634
635      for (int i = 0; i < sortedVals.length; i++) {
636        long decoded = OrderedBytes.decodeInt64(pbr.set(encoded[i]));
637        assertEquals(
638          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
639            sortedVals[i], decoded, ord),
640          sortedVals[i].longValue(), decoded);
641      }
642    }
643  }
644
645  /**
646   * Test float32 encoding.
647   */
648  @Test
649  public void testFloat32() {
650    Float[] vals =
651      { Float.MIN_VALUE, Float.MIN_VALUE + 1.0f, 0.0f, Float.MAX_VALUE / 2.0f, Float.MAX_VALUE };
652
653    /*
654     * assert encoded values match decoded values. encode into target buffer starting at an offset
655     * to detect over/underflow conditions.
656     */
657    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
658      for (Float val : vals) {
659        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
660        byte[] a = new byte[5 + 3];
661        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, 5 + 1);
662        buf1.setPosition(1);
663
664        // verify encode
665        assertEquals("Surprising return value.", 5, OrderedBytes.encodeFloat32(buf1, val, ord));
666        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
667          buf1.getPosition());
668        assertEquals("Surprising serialized length.", 5, buf1.getPosition() - 1);
669        assertEquals("Buffer underflow.", 0, a[0]);
670        assertEquals("Buffer underflow.", 0, a[1]);
671        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
672
673        // verify skip
674        buf1.setPosition(1);
675        assertEquals("Surprising return value.", 5, OrderedBytes.skip(buf1));
676        assertEquals("Did not skip enough bytes.", 5, buf1.getPosition() - 1);
677
678        // verify decode
679        buf1.setPosition(1);
680        assertEquals("Deserialization failed.", Float.floatToIntBits(val),
681          Float.floatToIntBits(OrderedBytes.decodeFloat32(buf1)));
682        assertEquals("Did not consume enough bytes.", 5, buf1.getPosition() - 1);
683      }
684    }
685
686    /*
687     * assert natural sort order is preserved by the codec.
688     */
689    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
690      byte[][] encoded = new byte[vals.length][5];
691      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
692      for (int i = 0; i < vals.length; i++) {
693        OrderedBytes.encodeFloat32(pbr.set(encoded[i]), vals[i], ord);
694      }
695
696      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
697      Float[] sortedVals = Arrays.copyOf(vals, vals.length);
698
699      if (ord == Order.ASCENDING) {
700        Arrays.sort(sortedVals);
701      } else {
702        Arrays.sort(sortedVals, Collections.reverseOrder());
703      }
704
705      for (int i = 0; i < sortedVals.length; i++) {
706        float decoded = OrderedBytes.decodeFloat32(pbr.set(encoded[i]));
707        assertEquals(
708          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
709            sortedVals[i], decoded, ord),
710          Float.floatToIntBits(sortedVals[i]), Float.floatToIntBits(decoded));
711      }
712    }
713  }
714
715  /**
716   * Test float64 encoding.
717   */
718  @Test
719  public void testFloat64() {
720    Double[] vals =
721      { Double.MIN_VALUE, Double.MIN_VALUE + 1.0, 0.0, Double.MAX_VALUE / 2.0, Double.MAX_VALUE };
722
723    /*
724     * assert encoded values match decoded values. encode into target buffer starting at an offset
725     * to detect over/underflow conditions.
726     */
727    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
728      for (Double val : vals) {
729        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
730        byte[] a = new byte[9 + 3];
731        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, 9 + 1);
732        buf1.setPosition(1);
733
734        // verify encode
735        assertEquals("Surprising return value.", 9, OrderedBytes.encodeFloat64(buf1, val, ord));
736        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
737          buf1.getPosition());
738        assertEquals("Surprising serialized length.", 9, buf1.getPosition() - 1);
739        assertEquals("Buffer underflow.", 0, a[0]);
740        assertEquals("Buffer underflow.", 0, a[1]);
741        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
742
743        // verify skip
744        buf1.setPosition(1);
745        assertEquals("Surprising return value.", 9, OrderedBytes.skip(buf1));
746        assertEquals("Did not skip enough bytes.", 9, buf1.getPosition() - 1);
747
748        // verify decode
749        buf1.setPosition(1);
750        assertEquals("Deserialization failed.", Double.doubleToLongBits(val),
751          Double.doubleToLongBits(OrderedBytes.decodeFloat64(buf1)));
752        assertEquals("Did not consume enough bytes.", 9, buf1.getPosition() - 1);
753      }
754    }
755
756    /*
757     * assert natural sort order is preserved by the codec.
758     */
759    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
760      byte[][] encoded = new byte[vals.length][9];
761      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
762      for (int i = 0; i < vals.length; i++) {
763        OrderedBytes.encodeFloat64(pbr.set(encoded[i]), vals[i], ord);
764      }
765
766      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
767      Double[] sortedVals = Arrays.copyOf(vals, vals.length);
768
769      if (ord == Order.ASCENDING) {
770        Arrays.sort(sortedVals);
771      } else {
772        Arrays.sort(sortedVals, Collections.reverseOrder());
773      }
774
775      for (int i = 0; i < sortedVals.length; i++) {
776        double decoded = OrderedBytes.decodeFloat64(pbr.set(encoded[i]));
777        assertEquals(
778          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
779            sortedVals[i], decoded, ord),
780          Double.doubleToLongBits(sortedVals[i]), Double.doubleToLongBits(decoded));
781      }
782    }
783  }
784
785  /**
786   * Test string encoding.
787   */
788  @Test
789  public void testString() {
790    String[] vals = { "foo", "baaaar", "bazz" };
791    int[] expectedLengths = { 5, 8, 6 };
792
793    /*
794     * assert encoded values match decoded values. encode into target buffer starting at an offset
795     * to detect over/underflow conditions.
796     */
797    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
798      for (int i = 0; i < vals.length; i++) {
799        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
800        byte[] a = new byte[expectedLengths[i] + 3];
801        PositionedByteRange buf1 =
802          new SimplePositionedMutableByteRange(a, 1, expectedLengths[i] + 1);
803        buf1.setPosition(1);
804
805        // verify encode
806        assertEquals("Surprising return value.", expectedLengths[i],
807          OrderedBytes.encodeString(buf1, vals[i], ord));
808        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
809          buf1.getPosition());
810        assertEquals("Surprising serialized length.", expectedLengths[i], buf1.getPosition() - 1);
811        assertEquals("Buffer underflow.", 0, a[0]);
812        assertEquals("Buffer underflow.", 0, a[1]);
813        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
814
815        // verify skip
816        buf1.setPosition(1);
817        assertEquals("Surprising return value.", expectedLengths[i], OrderedBytes.skip(buf1));
818        assertEquals("Did not skip enough bytes.", expectedLengths[i], buf1.getPosition() - 1);
819
820        // verify decode
821        buf1.setPosition(1);
822        assertEquals("Deserialization failed.", vals[i], OrderedBytes.decodeString(buf1));
823        assertEquals("Did not consume enough bytes.", expectedLengths[i], buf1.getPosition() - 1);
824      }
825    }
826
827    /*
828     * assert natural sort order is preserved by the codec.
829     */
830    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
831      byte[][] encoded = new byte[vals.length][];
832      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
833      for (int i = 0; i < vals.length; i++) {
834        encoded[i] = new byte[expectedLengths[i]];
835        OrderedBytes.encodeString(pbr.set(encoded[i]), vals[i], ord);
836      }
837
838      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
839      String[] sortedVals = Arrays.copyOf(vals, vals.length);
840
841      if (ord == Order.ASCENDING) {
842        Arrays.sort(sortedVals);
843      } else {
844        Arrays.sort(sortedVals, Collections.reverseOrder());
845      }
846
847      for (int i = 0; i < sortedVals.length; i++) {
848        pbr.set(encoded[i]);
849        String decoded = OrderedBytes.decodeString(pbr);
850        assertEquals(
851          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
852            sortedVals[i], decoded, ord),
853          sortedVals[i], decoded);
854      }
855    }
856  }
857
858  @Test(expected = IllegalArgumentException.class)
859  public void testStringNoNullChars() {
860    PositionedByteRange buff = new SimplePositionedMutableByteRange(3);
861    OrderedBytes.encodeString(buff, "\u0000", Order.ASCENDING);
862  }
863
864  /**
865   * Test length estimation algorithms for BlobVar encoding. Does not cover 0-length input case
866   * properly.
867   */
868  @Test
869  public void testBlobVarLencodedLength() {
870    int[][] values = {
871      /*
872       * decoded length, encoded length ceil((n bytes * 8 bits/input byte) / 7 bits/encoded byte) +
873       * 1 header
874       */
875      { 1, 3 }, { 2, 4 }, { 3, 5 }, { 4, 6 }, { 5, 7 }, { 6, 8 }, { 7, 9 }, { 8, 11 } };
876
877    for (int[] pair : values) {
878      assertEquals(pair[1], OrderedBytes.blobVarEncodedLength(pair[0]));
879      assertEquals(pair[0], OrderedBytes.blobVarDecodedLength(pair[1]));
880    }
881  }
882
883  /**
884   * Test BlobVar encoding.
885   */
886  @Test
887  public void testBlobVar() {
888    byte[][] vals = { Bytes.toBytes(""), Bytes.toBytes("foo"), Bytes.toBytes("foobarbazbub"),
889      { (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa,
890        (byte) 0xaa, /* 7 bytes of alternating bits; testing around HBASE-9893 */ },
891      { (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa,
892        (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa },
893      { (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa,
894        (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa,
895        (byte) 0xaa, /* 14 bytes of alternating bits; testing around HBASE-9893 */ },
896      { (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55,
897        (byte) 0x55, /* 7 bytes of alternating bits; testing around HBASE-9893 */ },
898      { (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55,
899        (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55 },
900      { (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55,
901        (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55,
902        (byte) 0x55, /* 14 bytes of alternating bits; testing around HBASE-9893 */ },
903      Bytes.toBytes("1"), Bytes.toBytes("22"), Bytes.toBytes("333"), Bytes.toBytes("4444"),
904      Bytes.toBytes("55555"), Bytes.toBytes("666666"), Bytes.toBytes("7777777"),
905      Bytes.toBytes("88888888") };
906
907    /*
908     * assert encoded values match decoded values. encode into target buffer starting at an offset
909     * to detect over/underflow conditions.
910     */
911    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
912      for (byte[] val : vals) {
913        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
914        int expectedLen = OrderedBytes.blobVarEncodedLength(val.length);
915        byte[] a = new byte[expectedLen + 3];
916        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, expectedLen + 1);
917        buf1.setPosition(1);
918
919        // verify encode
920        assertEquals("Surprising return value.", expectedLen,
921          OrderedBytes.encodeBlobVar(buf1, val, ord));
922        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
923          buf1.getPosition());
924        assertEquals("Surprising serialized length.", expectedLen, buf1.getPosition() - 1);
925        assertEquals("Buffer underflow.", 0, a[0]);
926        assertEquals("Buffer underflow.", 0, a[1]);
927        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
928
929        // verify skip
930        buf1.setPosition(1);
931        assertEquals("Surprising return value.", expectedLen, OrderedBytes.skip(buf1));
932        assertEquals("Did not skip enough bytes.", expectedLen, buf1.getPosition() - 1);
933
934        // verify decode
935        buf1.setPosition(1);
936        assertArrayEquals("Deserialization failed.", val, OrderedBytes.decodeBlobVar(buf1));
937        assertEquals("Did not consume enough bytes.", expectedLen, buf1.getPosition() - 1);
938      }
939    }
940
941    /*
942     * assert natural sort order is preserved by the codec.
943     */
944    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
945      byte[][] encoded = new byte[vals.length][];
946      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
947      for (int i = 0; i < vals.length; i++) {
948        encoded[i] = new byte[OrderedBytes.blobVarEncodedLength(vals[i].length)];
949        OrderedBytes.encodeBlobVar(pbr.set(encoded[i]), vals[i], ord);
950      }
951
952      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
953      byte[][] sortedVals = Arrays.copyOf(vals, vals.length);
954
955      if (ord == Order.ASCENDING) {
956        Arrays.sort(sortedVals, Bytes.BYTES_COMPARATOR);
957      } else {
958        Arrays.sort(sortedVals, Collections.reverseOrder(Bytes.BYTES_COMPARATOR));
959      }
960
961      for (int i = 0; i < sortedVals.length; i++) {
962        pbr.set(encoded[i]);
963        byte[] decoded = OrderedBytes.decodeBlobVar(pbr);
964        assertArrayEquals(
965          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
966            Arrays.toString(sortedVals[i]), Arrays.toString(decoded), ord),
967          sortedVals[i], decoded);
968      }
969    }
970  }
971
972  /**
973   * Test BlobCopy encoding.
974   */
975  @Test
976  public void testBlobCopy() {
977    byte[][] vals = { Bytes.toBytes(""), Bytes.toBytes("foo"), Bytes.toBytes("foobarbazbub"),
978      { (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa,
979        (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa, (byte) 0xaa },
980      { (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55,
981        (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55, (byte) 0x55 }, };
982
983    /*
984     * assert encoded values match decoded values. encode into target buffer starting at an offset
985     * to detect over/underflow conditions.
986     */
987    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
988      for (byte[] val : vals) {
989        // allocate a buffer 3-bytes larger than necessary to detect over/underflow
990        int expectedLen = val.length + (Order.ASCENDING == ord ? 1 : 2);
991        byte[] a = new byte[expectedLen + 3];
992        PositionedByteRange buf1 = new SimplePositionedMutableByteRange(a, 1, expectedLen + 1);
993        buf1.setPosition(1);
994
995        // verify encode
996        assertEquals("Surprising return value.", expectedLen,
997          OrderedBytes.encodeBlobCopy(buf1, val, ord));
998        assertEquals("Broken test: serialization did not consume entire buffer.", buf1.getLength(),
999          buf1.getPosition());
1000        assertEquals("Surprising serialized length.", expectedLen, buf1.getPosition() - 1);
1001        assertEquals("Buffer underflow.", 0, a[0]);
1002        assertEquals("Buffer underflow.", 0, a[1]);
1003        assertEquals("Buffer overflow.", 0, a[a.length - 1]);
1004
1005        // verify skip
1006        buf1.setPosition(1);
1007        assertEquals("Surprising return value.", expectedLen, OrderedBytes.skip(buf1));
1008        assertEquals("Did not skip enough bytes.", expectedLen, buf1.getPosition() - 1);
1009
1010        // verify decode
1011        buf1.setPosition(1);
1012        assertArrayEquals("Deserialization failed.", val, OrderedBytes.decodeBlobCopy(buf1));
1013        assertEquals("Did not consume enough bytes.", expectedLen, buf1.getPosition() - 1);
1014      }
1015    }
1016
1017    /*
1018     * assert natural sort order is preserved by the codec.
1019     */
1020    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
1021      byte[][] encoded = new byte[vals.length][];
1022      PositionedByteRange pbr = new SimplePositionedMutableByteRange();
1023      for (int i = 0; i < vals.length; i++) {
1024        encoded[i] = new byte[vals[i].length + (Order.ASCENDING == ord ? 1 : 2)];
1025        OrderedBytes.encodeBlobCopy(pbr.set(encoded[i]), vals[i], ord);
1026      }
1027
1028      Arrays.sort(encoded, Bytes.BYTES_COMPARATOR);
1029      byte[][] sortedVals = Arrays.copyOf(vals, vals.length);
1030
1031      if (ord == Order.ASCENDING) {
1032        Arrays.sort(sortedVals, Bytes.BYTES_COMPARATOR);
1033      } else {
1034        Arrays.sort(sortedVals, Collections.reverseOrder(Bytes.BYTES_COMPARATOR));
1035      }
1036
1037      for (int i = 0; i < sortedVals.length; i++) {
1038        pbr.set(encoded[i]);
1039        byte[] decoded = OrderedBytes.decodeBlobCopy(pbr);
1040        assertArrayEquals(
1041          String.format("Encoded representations do not preserve natural order: <%s>, <%s>, %s",
1042            Arrays.toString(sortedVals[i]), Arrays.toString(decoded), ord),
1043          sortedVals[i], decoded);
1044      }
1045    }
1046
1047    /*
1048     * assert byte[] segments are serialized correctly.
1049     */
1050    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
1051      byte[] a = new byte[3 + (Order.ASCENDING == ord ? 1 : 2) + 2];
1052      PositionedByteRange buf =
1053        new SimplePositionedMutableByteRange(a, 1, 3 + (Order.ASCENDING == ord ? 1 : 2));
1054      OrderedBytes.encodeBlobCopy(buf, Bytes.toBytes("foobarbaz"), 3, 3, ord);
1055      buf.setPosition(0);
1056      assertArrayEquals(Bytes.toBytes("bar"), OrderedBytes.decodeBlobCopy(buf));
1057    }
1058  }
1059
1060  /**
1061   * Assert invalid input byte[] are rejected by BlobCopy
1062   */
1063  @Test(expected = IllegalArgumentException.class)
1064  public void testBlobCopyNoZeroBytes() {
1065    byte[] val = { 0x01, 0x02, 0x00, 0x03 };
1066    // TODO: implementation detail leaked here.
1067    byte[] ascExpected = { 0x38, 0x01, 0x02, 0x00, 0x03 };
1068    PositionedByteRange buf = new SimplePositionedMutableByteRange(val.length + 1);
1069    OrderedBytes.encodeBlobCopy(buf, val, Order.ASCENDING);
1070    assertArrayEquals(ascExpected, buf.getBytes());
1071    buf.set(val.length + 2);
1072    OrderedBytes.encodeBlobCopy(buf, val, Order.DESCENDING);
1073    fail("test should never get here.");
1074  }
1075
1076  /**
1077   * Test generic skip logic
1078   */
1079  @Test
1080  public void testSkip() {
1081    BigDecimal longMax = BigDecimal.valueOf(Long.MAX_VALUE);
1082    double negInf = Double.NEGATIVE_INFINITY;
1083    BigDecimal negLarge = longMax.multiply(longMax).negate();
1084    BigDecimal negMed = new BigDecimal("-10.0");
1085    BigDecimal negSmall = new BigDecimal("-0.0010");
1086    long zero = 0L;
1087    BigDecimal posSmall = negSmall.negate();
1088    BigDecimal posMed = negMed.negate();
1089    BigDecimal posLarge = negLarge.negate();
1090    double posInf = Double.POSITIVE_INFINITY;
1091    double nan = Double.NaN;
1092    byte int8 = 100;
1093    short int16 = 100;
1094    int int32 = 100;
1095    long int64 = 100L;
1096    float float32 = 100.0f;
1097    double float64 = 100.0d;
1098    String text = "hello world.";
1099    byte[] blobVar = Bytes.toBytes("foo");
1100    byte[] blobCopy = Bytes.toBytes("bar");
1101
1102    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
1103      PositionedByteRange buff = new SimplePositionedMutableByteRange(30);
1104      int o;
1105      o = OrderedBytes.encodeNull(buff, ord);
1106      buff.setPosition(0);
1107      assertEquals(o, OrderedBytes.skip(buff));
1108
1109      buff.setPosition(0);
1110      o = OrderedBytes.encodeNumeric(buff, negInf, ord);
1111      buff.setPosition(0);
1112      assertEquals(o, OrderedBytes.skip(buff));
1113
1114      buff.setPosition(0);
1115      o = OrderedBytes.encodeNumeric(buff, negLarge, ord);
1116      buff.setPosition(0);
1117      assertEquals(o, OrderedBytes.skip(buff));
1118
1119      buff.setPosition(0);
1120      o = OrderedBytes.encodeNumeric(buff, negMed, ord);
1121      buff.setPosition(0);
1122      assertEquals(o, OrderedBytes.skip(buff));
1123
1124      buff.setPosition(0);
1125      o = OrderedBytes.encodeNumeric(buff, negSmall, ord);
1126      buff.setPosition(0);
1127      assertEquals(o, OrderedBytes.skip(buff));
1128
1129      buff.setPosition(0);
1130      o = OrderedBytes.encodeNumeric(buff, zero, ord);
1131      buff.setPosition(0);
1132      assertEquals(o, OrderedBytes.skip(buff));
1133
1134      buff.setPosition(0);
1135      o = OrderedBytes.encodeNumeric(buff, posSmall, ord);
1136      buff.setPosition(0);
1137      assertEquals(o, OrderedBytes.skip(buff));
1138
1139      buff.setPosition(0);
1140      o = OrderedBytes.encodeNumeric(buff, posMed, ord);
1141      buff.setPosition(0);
1142      assertEquals(o, OrderedBytes.skip(buff));
1143
1144      buff.setPosition(0);
1145      o = OrderedBytes.encodeNumeric(buff, posLarge, ord);
1146      buff.setPosition(0);
1147      assertEquals(o, OrderedBytes.skip(buff));
1148
1149      buff.setPosition(0);
1150      o = OrderedBytes.encodeNumeric(buff, posInf, ord);
1151      buff.setPosition(0);
1152      assertEquals(o, OrderedBytes.skip(buff));
1153
1154      buff.setPosition(0);
1155      o = OrderedBytes.encodeNumeric(buff, nan, ord);
1156      buff.setPosition(0);
1157      assertEquals(o, OrderedBytes.skip(buff));
1158
1159      buff.setPosition(0);
1160      o = OrderedBytes.encodeInt8(buff, int8, ord);
1161      buff.setPosition(0);
1162      assertEquals(o, OrderedBytes.skip(buff));
1163
1164      buff.setPosition(0);
1165      o = OrderedBytes.encodeInt16(buff, int16, ord);
1166      buff.setPosition(0);
1167      assertEquals(o, OrderedBytes.skip(buff));
1168
1169      buff.setPosition(0);
1170      o = OrderedBytes.encodeInt32(buff, int32, ord);
1171      buff.setPosition(0);
1172      assertEquals(o, OrderedBytes.skip(buff));
1173
1174      buff.setPosition(0);
1175      o = OrderedBytes.encodeInt64(buff, int64, ord);
1176      buff.setPosition(0);
1177      assertEquals(o, OrderedBytes.skip(buff));
1178
1179      buff.setPosition(0);
1180      o = OrderedBytes.encodeFloat32(buff, float32, ord);
1181      buff.setPosition(0);
1182      assertEquals(o, OrderedBytes.skip(buff));
1183
1184      buff.setPosition(0);
1185      o = OrderedBytes.encodeFloat64(buff, float64, ord);
1186      buff.setPosition(0);
1187      assertEquals(o, OrderedBytes.skip(buff));
1188
1189      buff.setPosition(0);
1190      o = OrderedBytes.encodeString(buff, text, ord);
1191      buff.setPosition(0);
1192      assertEquals(o, OrderedBytes.skip(buff));
1193
1194      buff.setPosition(0);
1195      o = OrderedBytes.encodeBlobVar(buff, blobVar, ord);
1196      buff.setPosition(0);
1197      assertEquals(o, OrderedBytes.skip(buff));
1198
1199      // blobCopy is special in that it runs to the end of the target buffer.
1200      buff.set(blobCopy.length + (Order.ASCENDING == ord ? 1 : 2));
1201      o = OrderedBytes.encodeBlobCopy(buff, blobCopy, ord);
1202      buff.setPosition(0);
1203      assertEquals(o, OrderedBytes.skip(buff));
1204    }
1205  }
1206
1207  /**
1208   * Test encoded value check
1209   */
1210  @Test
1211  public void testEncodedValueCheck() {
1212    BigDecimal longMax = BigDecimal.valueOf(Long.MAX_VALUE);
1213    double negInf = Double.NEGATIVE_INFINITY;
1214    BigDecimal negLarge = longMax.multiply(longMax).negate();
1215    BigDecimal negMed = new BigDecimal("-10.0");
1216    BigDecimal negSmall = new BigDecimal("-0.0010");
1217    long zero = 0L;
1218    BigDecimal posSmall = negSmall.negate();
1219    BigDecimal posMed = negMed.negate();
1220    BigDecimal posLarge = negLarge.negate();
1221    double posInf = Double.POSITIVE_INFINITY;
1222    double nan = Double.NaN;
1223    byte int8 = 100;
1224    short int16 = 100;
1225    int int32 = 100;
1226    long int64 = 100L;
1227    float float32 = 100.0f;
1228    double float64 = 100.0d;
1229    String text = "hello world.";
1230    byte[] blobVar = Bytes.toBytes("foo");
1231
1232    int cnt = 0;
1233    PositionedByteRange buff = new SimplePositionedMutableByteRange(1024);
1234    for (Order ord : new Order[] { Order.ASCENDING, Order.DESCENDING }) {
1235      OrderedBytes.encodeNull(buff, ord);
1236      cnt++;
1237      OrderedBytes.encodeNumeric(buff, negInf, ord);
1238      cnt++;
1239      OrderedBytes.encodeNumeric(buff, negLarge, ord);
1240      cnt++;
1241      OrderedBytes.encodeNumeric(buff, negMed, ord);
1242      cnt++;
1243      OrderedBytes.encodeNumeric(buff, negSmall, ord);
1244      cnt++;
1245      OrderedBytes.encodeNumeric(buff, zero, ord);
1246      cnt++;
1247      OrderedBytes.encodeNumeric(buff, posSmall, ord);
1248      cnt++;
1249      OrderedBytes.encodeNumeric(buff, posMed, ord);
1250      cnt++;
1251      OrderedBytes.encodeNumeric(buff, posLarge, ord);
1252      cnt++;
1253      OrderedBytes.encodeNumeric(buff, posInf, ord);
1254      cnt++;
1255      OrderedBytes.encodeNumeric(buff, nan, ord);
1256      cnt++;
1257      OrderedBytes.encodeInt8(buff, int8, ord);
1258      cnt++;
1259      OrderedBytes.encodeInt16(buff, int16, ord);
1260      cnt++;
1261      OrderedBytes.encodeInt32(buff, int32, ord);
1262      cnt++;
1263      OrderedBytes.encodeInt64(buff, int64, ord);
1264      cnt++;
1265      OrderedBytes.encodeFloat32(buff, float32, ord);
1266      cnt++;
1267      OrderedBytes.encodeFloat64(buff, float64, ord);
1268      cnt++;
1269      OrderedBytes.encodeString(buff, text, ord);
1270      cnt++;
1271      OrderedBytes.encodeBlobVar(buff, blobVar, ord);
1272      cnt++;
1273    }
1274
1275    buff.setPosition(0);
1276    assertEquals(OrderedBytes.length(buff), cnt);
1277    for (int i = 0; i < cnt; i++) {
1278      assertTrue(OrderedBytes.isEncodedValue(buff));
1279      OrderedBytes.skip(buff);
1280    }
1281  }
1282
1283  /**
1284   * Test if the data encoded by our encoding function can be decoded correctly.
1285   */
1286  @Test
1287  public void testEncodeDecodeMatch() {
1288    int samplesQuantity = 200;
1289    for (int i = 0; i < samplesQuantity; i++) {
1290      BigDecimal randomData = BigDecimal
1291        .valueOf(ThreadLocalRandom.current().nextDouble() + ThreadLocalRandom.current().nextLong());
1292      PositionedByteRange tmp = new SimplePositionedMutableByteRange(100);
1293      Order ord = ThreadLocalRandom.current().nextBoolean() ? Order.DESCENDING : Order.ASCENDING;
1294
1295      OrderedBytes.encodeNumeric(tmp, randomData, ord);
1296      tmp.setPosition(0);
1297
1298      BigDecimal left = OrderedBytes.normalize(randomData);
1299      BigDecimal right = OrderedBytes.decodeNumericAsBigDecimal(tmp);
1300      assertEquals(0, left.compareTo(right));
1301    }
1302  }
1303}