1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.hadoop.hbase.util;
19
20 import static org.apache.hadoop.hbase.util.Order.ASCENDING;
21 import static org.apache.hadoop.hbase.util.Order.DESCENDING;
22
23 import java.math.BigDecimal;
24 import java.math.BigInteger;
25 import java.math.MathContext;
26 import java.math.RoundingMode;
27 import java.nio.charset.Charset;
28
29 import org.apache.hadoop.hbase.classification.InterfaceAudience;
30 import org.apache.hadoop.hbase.classification.InterfaceStability;
31
32 import com.google.common.annotations.VisibleForTesting;
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269 @InterfaceAudience.Public
270 @InterfaceStability.Evolving
271 public class OrderedBytes {
272
273
274
275
276
277
278
279
280
281 private static final byte NULL = 0x05;
282
283 private static final byte NEG_INF = 0x07;
284 private static final byte NEG_LARGE = 0x08;
285 private static final byte NEG_MED_MIN = 0x09;
286 private static final byte NEG_MED_MAX = 0x13;
287 private static final byte NEG_SMALL = 0x14;
288 private static final byte ZERO = 0x15;
289 private static final byte POS_SMALL = 0x16;
290 private static final byte POS_MED_MIN = 0x17;
291 private static final byte POS_MED_MAX = 0x21;
292 private static final byte POS_LARGE = 0x22;
293 private static final byte POS_INF = 0x23;
294
295 private static final byte NAN = 0x26;
296
297 private static final byte FIXED_INT8 = 0x29;
298 private static final byte FIXED_INT16 = 0x2a;
299 private static final byte FIXED_INT32 = 0x2b;
300 private static final byte FIXED_INT64 = 0x2c;
301
302 private static final byte FIXED_FLOAT32 = 0x30;
303 private static final byte FIXED_FLOAT64 = 0x31;
304
305 private static final byte TEXT = 0x34;
306
307 private static final byte BLOB_VAR = 0x37;
308 private static final byte BLOB_COPY = 0x38;
309
310
311
312
313
314 public static final Charset UTF8 = Charset.forName("UTF-8");
315 private static final byte TERM = 0x00;
316 private static final BigDecimal E8 = BigDecimal.valueOf(1e8);
317 private static final BigDecimal E32 = BigDecimal.valueOf(1e32);
318 private static final BigDecimal EN2 = BigDecimal.valueOf(1e-2);
319 private static final BigDecimal EN10 = BigDecimal.valueOf(1e-10);
320
321
322
323
324 public static final int MAX_PRECISION = 31;
325
326
327
328
329 public static final MathContext DEFAULT_MATH_CONTEXT =
330 new MathContext(MAX_PRECISION, RoundingMode.HALF_UP);
331
332
333
334
335
336
337 private static IllegalArgumentException unexpectedHeader(byte header) {
338 throw new IllegalArgumentException("unexpected value in first byte: 0x"
339 + Long.toHexString(header));
340 }
341
342
343
344
345
346 private static int unsignedCmp(long x1, long x2) {
347 int cmp;
348 if ((cmp = (x1 < x2 ? -1 : (x1 == x2 ? 0 : 1))) == 0) return 0;
349
350 if ((x1 < 0) != (x2 < 0)) return -cmp;
351 return cmp;
352 }
353
354
355
356
357
358 private static int putUint32(PositionedByteRange dst, int val) {
359 dst.put((byte) (val >>> 24))
360 .put((byte) (val >>> 16))
361 .put((byte) (val >>> 8))
362 .put((byte) val);
363 return 4;
364 }
365
366
367
368
369
370
371
372
373 @VisibleForTesting
374 static int putVaruint64(PositionedByteRange dst, long val, boolean comp) {
375 int w, y, len = 0;
376 final int offset = dst.getOffset(), start = dst.getPosition();
377 byte[] a = dst.getBytes();
378 Order ord = comp ? DESCENDING : ASCENDING;
379 if (-1 == unsignedCmp(val, 241L)) {
380 dst.put((byte) val);
381 len = dst.getPosition() - start;
382 ord.apply(a, offset + start, len);
383 return len;
384 }
385 if (-1 == unsignedCmp(val, 2288L)) {
386 y = (int) (val - 240);
387 dst.put((byte) (y / 256 + 241))
388 .put((byte) (y % 256));
389 len = dst.getPosition() - start;
390 ord.apply(a, offset + start, len);
391 return len;
392 }
393 if (-1 == unsignedCmp(val, 67824L)) {
394 y = (int) (val - 2288);
395 dst.put((byte) 249)
396 .put((byte) (y / 256))
397 .put((byte) (y % 256));
398 len = dst.getPosition() - start;
399 ord.apply(a, offset + start, len);
400 return len;
401 }
402 y = (int) val;
403 w = (int) (val >>> 32);
404 if (w == 0) {
405 if (-1 == unsignedCmp(y, 16777216L)) {
406 dst.put((byte) 250)
407 .put((byte) (y >>> 16))
408 .put((byte) (y >>> 8))
409 .put((byte) y);
410 len = dst.getPosition() - start;
411 ord.apply(a, offset + start, len);
412 return len;
413 }
414 dst.put((byte) 251);
415 putUint32(dst, y);
416 len = dst.getPosition() - start;
417 ord.apply(a, offset + start, len);
418 return len;
419 }
420 if (-1 == unsignedCmp(w, 256L)) {
421 dst.put((byte) 252)
422 .put((byte) w);
423 putUint32(dst, y);
424 len = dst.getPosition() - start;
425 ord.apply(a, offset + start, len);
426 return len;
427 }
428 if (-1 == unsignedCmp(w, 65536L)) {
429 dst.put((byte) 253)
430 .put((byte) (w >>> 8))
431 .put((byte) w);
432 putUint32(dst, y);
433 len = dst.getPosition() - start;
434 ord.apply(a, offset + start, len);
435 return len;
436 }
437 if (-1 == unsignedCmp(w, 16777216L)) {
438 dst.put((byte) 254)
439 .put((byte) (w >>> 16))
440 .put((byte) (w >>> 8))
441 .put((byte) w);
442 putUint32(dst, y);
443 len = dst.getPosition() - start;
444 ord.apply(a, offset + start, len);
445 return len;
446 }
447 dst.put((byte) 255);
448 putUint32(dst, w);
449 putUint32(dst, y);
450 len = dst.getPosition() - start;
451 ord.apply(a, offset + start, len);
452 return len;
453 }
454
455
456
457
458
459
460
461
462 @VisibleForTesting
463 static int lengthVaruint64(PositionedByteRange src, boolean comp) {
464 int a0 = (comp ? DESCENDING : ASCENDING).apply(src.peek()) & 0xff;
465 if (a0 <= 240) return 1;
466 if (a0 <= 248) return 2;
467 if (a0 == 249) return 3;
468 if (a0 == 250) return 4;
469 if (a0 == 251) return 5;
470 if (a0 == 252) return 6;
471 if (a0 == 253) return 7;
472 if (a0 == 254) return 8;
473 if (a0 == 255) return 9;
474 throw unexpectedHeader(src.peek());
475 }
476
477
478
479
480
481
482
483 @VisibleForTesting
484 static int skipVaruint64(PositionedByteRange src, boolean cmp) {
485 final int len = lengthVaruint64(src, cmp);
486 src.setPosition(src.getPosition() + len);
487 return len;
488 }
489
490
491
492
493
494
495 @VisibleForTesting
496 static long getVaruint64(PositionedByteRange src, boolean comp) {
497 assert src.getRemaining() >= lengthVaruint64(src, comp);
498 final long ret;
499 Order ord = comp ? DESCENDING : ASCENDING;
500 byte x = src.get();
501 final int a0 = ord.apply(x) & 0xff, a1, a2, a3, a4, a5, a6, a7, a8;
502 if (-1 == unsignedCmp(a0, 241)) {
503 return a0;
504 }
505 x = src.get();
506 a1 = ord.apply(x) & 0xff;
507 if (-1 == unsignedCmp(a0, 249)) {
508 return (a0 - 241) * 256 + a1 + 240;
509 }
510 x = src.get();
511 a2 = ord.apply(x) & 0xff;
512 if (a0 == 249) {
513 return 2288 + 256 * a1 + a2;
514 }
515 x = src.get();
516 a3 = ord.apply(x) & 0xff;
517 if (a0 == 250) {
518 return (a1 << 16) | (a2 << 8) | a3;
519 }
520 x = src.get();
521 a4 = ord.apply(x) & 0xff;
522 ret = (((long) a1) << 24) | (a2 << 16) | (a3 << 8) | a4;
523 if (a0 == 251) {
524 return ret;
525 }
526 x = src.get();
527 a5 = ord.apply(x) & 0xff;
528 if (a0 == 252) {
529 return (ret << 8) | a5;
530 }
531 x = src.get();
532 a6 = ord.apply(x) & 0xff;
533 if (a0 == 253) {
534 return (ret << 16) | (a5 << 8) | a6;
535 }
536 x = src.get();
537 a7 = ord.apply(x) & 0xff;
538 if (a0 == 254) {
539 return (ret << 24) | (a5 << 16) | (a6 << 8) | a7;
540 }
541 x = src.get();
542 a8 = ord.apply(x) & 0xff;
543 return (ret << 32) | (((long) a5) << 24) | (a6 << 16) | (a7 << 8) | a8;
544 }
545
546
547
548
549
550
551
552 @VisibleForTesting
553 static BigDecimal normalize(BigDecimal val) {
554 return null == val ? null : val.stripTrailingZeros().round(DEFAULT_MATH_CONTEXT);
555 }
556
557
558
559
560
561
562
563
564
565
566
567 private static BigDecimal decodeSignificand(PositionedByteRange src, int e, boolean comp) {
568
569 byte[] a = src.getBytes();
570 final int start = src.getPosition(), offset = src.getOffset(), remaining = src.getRemaining();
571 Order ord = comp ? DESCENDING : ASCENDING;
572 BigDecimal m = BigDecimal.ZERO;
573 e--;
574 for (int i = 0;; i++) {
575 if (i > remaining) {
576
577 src.setPosition(start);
578 throw new IllegalArgumentException(
579 "Read exceeds range before termination byte found. offset: " + offset + " position: "
580 + (start + i));
581 }
582
583 m = m.add(
584 new BigDecimal(BigInteger.ONE, e * -2).multiply(
585 BigDecimal.valueOf((ord.apply(a[offset + start + i]) & 0xff) / 2)));
586 e--;
587
588 if ((ord.apply(a[offset + start + i]) & 1) == 0) {
589 src.setPosition(start + i + 1);
590 break;
591 }
592 }
593 return normalize(m);
594 }
595
596
597
598
599
600
601
602 private static int skipSignificand(PositionedByteRange src, boolean comp) {
603 byte[] a = src.getBytes();
604 final int offset = src.getOffset(), start = src.getPosition();
605 int i = src.getPosition();
606 while (((comp ? DESCENDING : ASCENDING).apply(a[offset + i++]) & 1) != 0)
607 ;
608 src.setPosition(i);
609 return i - start;
610 }
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636 private static int encodeNumericSmall(PositionedByteRange dst, BigDecimal val) {
637
638
639 BigDecimal abs = val.abs();
640 assert BigDecimal.ZERO.compareTo(abs) < 0 && BigDecimal.ONE.compareTo(abs) > 0;
641 byte[] a = dst.getBytes();
642 boolean isNeg = val.signum() == -1;
643 final int offset = dst.getOffset(), start = dst.getPosition();
644 int e = 0, d, startM;
645
646 if (isNeg) {
647 dst.put(NEG_SMALL);
648 } else {
649 dst.put(POS_SMALL);
650 }
651
652
653 while (abs.compareTo(EN10) < 0) { abs = abs.movePointRight(8); e += 4; }
654 while (abs.compareTo(EN2) < 0) { abs = abs.movePointRight(2); e++; }
655
656 putVaruint64(dst, e, !isNeg);
657
658
659 startM = dst.getPosition();
660
661
662 for (int i = 0; i < 18 && abs.compareTo(BigDecimal.ZERO) != 0; i++) {
663 abs = abs.movePointRight(2);
664 d = abs.intValue();
665 dst.put((byte) ((2 * d + 1) & 0xff));
666 abs = abs.subtract(BigDecimal.valueOf(d));
667 }
668 a[offset + dst.getPosition() - 1] &= 0xfe;
669 if (isNeg) {
670
671 DESCENDING.apply(a, offset + startM, dst.getPosition() - startM);
672 }
673 return dst.getPosition() - start;
674 }
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712 private static int encodeNumericLarge(PositionedByteRange dst, BigDecimal val) {
713
714 BigDecimal abs = val.abs();
715 byte[] a = dst.getBytes();
716 boolean isNeg = val.signum() == -1;
717 final int start = dst.getPosition(), offset = dst.getOffset();
718 int e = 0, d, startM;
719
720 if (isNeg) {
721 dst.put(NEG_LARGE);
722 } else {
723 dst.put(POS_LARGE);
724 }
725
726
727 while (abs.compareTo(E32) >= 0 && e <= 350) { abs = abs.movePointLeft(32); e +=16; }
728 while (abs.compareTo(E8) >= 0 && e <= 350) { abs = abs.movePointLeft(8); e+= 4; }
729 while (abs.compareTo(BigDecimal.ONE) >= 0 && e <= 350) { abs = abs.movePointLeft(2); e++; }
730
731
732 if (e > 10) {
733 putVaruint64(dst, e, isNeg);
734 } else {
735 if (isNeg) {
736 dst.put(start, (byte) (NEG_MED_MAX - e));
737 } else {
738 dst.put(start, (byte) (POS_MED_MIN + e));
739 }
740 }
741
742
743 startM = dst.getPosition();
744
745
746 for (int i = 0; i < 18 && abs.compareTo(BigDecimal.ZERO) != 0; i++) {
747 abs = abs.movePointRight(2);
748 d = abs.intValue();
749 dst.put((byte) (2 * d + 1));
750 abs = abs.subtract(BigDecimal.valueOf(d));
751 }
752
753 a[offset + dst.getPosition() - 1] &= 0xfe;
754 if (isNeg) {
755
756 DESCENDING.apply(a, offset + startM, dst.getPosition() - startM);
757 }
758 return dst.getPosition() - start;
759 }
760
761
762
763
764
765
766
767
768 public static int encodeNumeric(PositionedByteRange dst, long val, Order ord) {
769 return encodeNumeric(dst, BigDecimal.valueOf(val), ord);
770 }
771
772
773
774
775
776
777
778
779 public static int encodeNumeric(PositionedByteRange dst, double val, Order ord) {
780 if (val == 0.0) {
781 dst.put(ord.apply(ZERO));
782 return 1;
783 }
784 if (Double.isNaN(val)) {
785 dst.put(ord.apply(NAN));
786 return 1;
787 }
788 if (val == Double.NEGATIVE_INFINITY) {
789 dst.put(ord.apply(NEG_INF));
790 return 1;
791 }
792 if (val == Double.POSITIVE_INFINITY) {
793 dst.put(ord.apply(POS_INF));
794 return 1;
795 }
796 return encodeNumeric(dst, BigDecimal.valueOf(val), ord);
797 }
798
799
800
801
802
803
804
805
806 public static int encodeNumeric(PositionedByteRange dst, BigDecimal val, Order ord) {
807 final int len, offset = dst.getOffset(), start = dst.getPosition();
808 if (null == val) {
809 return encodeNull(dst, ord);
810 } else if (BigDecimal.ZERO.compareTo(val) == 0) {
811 dst.put(ord.apply(ZERO));
812 return 1;
813 }
814 BigDecimal abs = val.abs();
815 if (BigDecimal.ONE.compareTo(abs) <= 0) {
816 len = encodeNumericLarge(dst, normalize(val));
817 } else {
818 len = encodeNumericSmall(dst, normalize(val));
819 }
820 ord.apply(dst.getBytes(), offset + start, len);
821 return len;
822 }
823
824
825
826
827
828
829
830
831 private static BigDecimal decodeNumericValue(PositionedByteRange src) {
832 final int e;
833 byte header = src.get();
834 boolean dsc = -1 == Integer.signum(header);
835 header = dsc ? DESCENDING.apply(header) : header;
836
837 if (header == NULL) return null;
838 if (header == NEG_LARGE) {
839 e = (int) getVaruint64(src, !dsc);
840 return decodeSignificand(src, e, !dsc).negate();
841 }
842 if (header >= NEG_MED_MIN && header <= NEG_MED_MAX) {
843
844 e = NEG_MED_MAX - header;
845 return decodeSignificand(src, e, !dsc).negate();
846 }
847 if (header == NEG_SMALL) {
848 e = (int) -getVaruint64(src, dsc);
849 return decodeSignificand(src, e, !dsc).negate();
850 }
851 if (header == ZERO) {
852 return BigDecimal.ZERO;
853 }
854 if (header == POS_SMALL) {
855 e = (int) -getVaruint64(src, !dsc);
856 return decodeSignificand(src, e, dsc);
857 }
858 if (header >= POS_MED_MIN && header <= POS_MED_MAX) {
859
860 e = header - POS_MED_MIN;
861 return decodeSignificand(src, e, dsc);
862 }
863 if (header == POS_LARGE) {
864 e = (int) getVaruint64(src, dsc);
865 return decodeSignificand(src, e, dsc);
866 }
867 throw unexpectedHeader(header);
868 }
869
870
871
872
873
874
875
876
877
878
879
880
881 public static double decodeNumericAsDouble(PositionedByteRange src) {
882
883 if (isNull(src)) {
884 throw new NullPointerException("A null value cannot be decoded to a double.");
885 }
886 if (isNumericNaN(src)) {
887 src.get();
888 return Double.NaN;
889 }
890 if (isNumericZero(src)) {
891 src.get();
892 return Double.valueOf(0.0);
893 }
894
895 byte header = -1 == Integer.signum(src.peek()) ? DESCENDING.apply(src.peek()) : src.peek();
896
897 if (header == NEG_INF) {
898 src.get();
899 return Double.NEGATIVE_INFINITY;
900 } else if (header == POS_INF) {
901 src.get();
902 return Double.POSITIVE_INFINITY;
903 } else {
904 return decodeNumericValue(src).doubleValue();
905 }
906 }
907
908
909
910
911
912
913
914
915
916
917
918
919 public static long decodeNumericAsLong(PositionedByteRange src) {
920
921 if (isNull(src)) throw new NullPointerException();
922 if (!isNumeric(src)) throw unexpectedHeader(src.peek());
923 if (isNumericNaN(src)) throw unexpectedHeader(src.peek());
924 if (isNumericInfinite(src)) throw unexpectedHeader(src.peek());
925
926 if (isNumericZero(src)) {
927 src.get();
928 return Long.valueOf(0);
929 }
930 return decodeNumericValue(src).longValue();
931 }
932
933
934
935
936
937
938 public static BigDecimal decodeNumericAsBigDecimal(PositionedByteRange src) {
939 if (isNull(src)) {
940 src.get();
941 return null;
942 }
943 if (!isNumeric(src)) throw unexpectedHeader(src.peek());
944 if (isNumericNaN(src)) throw unexpectedHeader(src.peek());
945 if (isNumericInfinite(src)) throw unexpectedHeader(src.peek());
946 return decodeNumericValue(src);
947 }
948
949
950
951
952
953
954
955
956
957
958 public static int encodeString(PositionedByteRange dst, String val, Order ord) {
959 if (null == val) {
960 return encodeNull(dst, ord);
961 }
962 if (val.contains("\u0000"))
963 throw new IllegalArgumentException("Cannot encode String values containing '\\u0000'");
964 final int offset = dst.getOffset(), start = dst.getPosition();
965 dst.put(TEXT);
966
967 dst.put(val.getBytes(UTF8));
968 dst.put(TERM);
969 ord.apply(dst.getBytes(), offset + start, dst.getPosition() - start);
970 return dst.getPosition() - start;
971 }
972
973
974
975
976 public static String decodeString(PositionedByteRange src) {
977 final byte header = src.get();
978 if (header == NULL || header == DESCENDING.apply(NULL))
979 return null;
980 assert header == TEXT || header == DESCENDING.apply(TEXT);
981 Order ord = header == TEXT ? ASCENDING : DESCENDING;
982 byte[] a = src.getBytes();
983 final int offset = src.getOffset(), start = src.getPosition();
984 final byte terminator = ord.apply(TERM);
985 int rawStartPos = offset + start, rawTermPos = rawStartPos;
986 for (; a[rawTermPos] != terminator; rawTermPos++)
987 ;
988 src.setPosition(rawTermPos - offset + 1);
989 if (DESCENDING == ord) {
990
991 byte[] copy = new byte[rawTermPos - rawStartPos];
992 System.arraycopy(a, rawStartPos, copy, 0, copy.length);
993 ord.apply(copy);
994 return new String(copy, UTF8);
995 } else {
996 return new String(a, rawStartPos, rawTermPos - rawStartPos, UTF8);
997 }
998 }
999
1000
1001
1002
1003 public static int blobVarEncodedLength(int len) {
1004 if (0 == len)
1005 return 2;
1006 else
1007 return (int)
1008 Math.ceil(
1009 (len * 8)
1010 / 7.0)
1011 + 1;
1012 }
1013
1014
1015
1016
1017 @VisibleForTesting
1018 static int blobVarDecodedLength(int len) {
1019 return
1020 ((len
1021 - 1)
1022 * 7)
1023 / 8;
1024 }
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041 public static int encodeBlobVar(PositionedByteRange dst, byte[] val, int voff, int vlen,
1042 Order ord) {
1043 if (null == val) {
1044 return encodeNull(dst, ord);
1045 }
1046
1047 assert dst.getRemaining() >= blobVarEncodedLength(vlen) : "buffer overflow expected.";
1048 final int offset = dst.getOffset(), start = dst.getPosition();
1049 dst.put(BLOB_VAR);
1050 if (0 == vlen) {
1051 dst.put(TERM);
1052 } else {
1053 byte s = 1, t = 0;
1054 for (int i = voff; i < vlen; i++) {
1055 dst.put((byte) (0x80 | t | ((val[i] & 0xff) >>> s)));
1056 if (s < 7) {
1057 t = (byte) (val[i] << (7 - s));
1058 s++;
1059 } else {
1060 dst.put((byte) (0x80 | val[i]));
1061 s = 1;
1062 t = 0;
1063 }
1064 }
1065 if (s > 1) {
1066 dst.put((byte) (0x7f & t));
1067 } else {
1068 dst.getBytes()[offset + dst.getPosition() - 1] &= 0x7f;
1069 }
1070 }
1071 ord.apply(dst.getBytes(), offset + start, dst.getPosition() - start);
1072 return dst.getPosition() - start;
1073 }
1074
1075
1076
1077
1078
1079
1080 public static int encodeBlobVar(PositionedByteRange dst, byte[] val, Order ord) {
1081 return encodeBlobVar(dst, val, 0, null != val ? val.length : 0, ord);
1082 }
1083
1084
1085
1086
1087 public static byte[] decodeBlobVar(PositionedByteRange src) {
1088 final byte header = src.get();
1089 if (header == NULL || header == DESCENDING.apply(NULL)) {
1090 return null;
1091 }
1092 assert header == BLOB_VAR || header == DESCENDING.apply(BLOB_VAR);
1093 Order ord = BLOB_VAR == header ? ASCENDING : DESCENDING;
1094 if (src.peek() == ord.apply(TERM)) {
1095
1096 src.get();
1097 return new byte[0];
1098 }
1099 final int offset = src.getOffset(), start = src.getPosition();
1100 int end;
1101 byte[] a = src.getBytes();
1102 for (end = start; (byte) (ord.apply(a[offset + end]) & 0x80) != TERM; end++)
1103 ;
1104 end++;
1105
1106 PositionedByteRange ret = new SimplePositionedMutableByteRange(blobVarDecodedLength(end - start
1107 + 1));
1108 int s = 6;
1109 byte t = (byte) ((ord.apply(a[offset + start]) << 1) & 0xff);
1110 for (int i = start + 1; i < end; i++) {
1111 if (s == 7) {
1112 ret.put((byte) (t | (ord.apply(a[offset + i]) & 0x7f)));
1113 i++;
1114
1115
1116 t = 0;
1117 } else {
1118 ret.put((byte) (t | ((ord.apply(a[offset + i]) & 0x7f) >>> s)));
1119 }
1120 if (i == end) break;
1121 t = (byte) ((ord.apply(a[offset + i]) << 8 - s) & 0xff);
1122 s = s == 1 ? 7 : s - 1;
1123 }
1124 src.setPosition(end);
1125 assert t == 0 : "Unexpected bits remaining after decoding blob.";
1126 assert ret.getPosition() == ret.getLength() : "Allocated unnecessarily large return buffer.";
1127 return ret.getBytes();
1128 }
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138 public static int encodeBlobCopy(PositionedByteRange dst, byte[] val, int voff, int vlen,
1139 Order ord) {
1140 if (null == val) {
1141 encodeNull(dst, ord);
1142 if (ASCENDING == ord) return 1;
1143 else {
1144
1145
1146 dst.put(ord.apply(TERM));
1147 return 2;
1148 }
1149 }
1150
1151 assert dst.getRemaining() >= vlen + (ASCENDING == ord ? 1 : 2);
1152 if (DESCENDING == ord) {
1153 for (int i = 0; i < vlen; i++) {
1154 if (TERM == val[voff + i]) {
1155 throw new IllegalArgumentException("0x00 bytes not permitted in value.");
1156 }
1157 }
1158 }
1159 final int offset = dst.getOffset(), start = dst.getPosition();
1160 dst.put(BLOB_COPY);
1161 dst.put(val, voff, vlen);
1162
1163
1164 if (DESCENDING == ord) dst.put(TERM);
1165 ord.apply(dst.getBytes(), offset + start, dst.getPosition() - start);
1166 return dst.getPosition() - start;
1167 }
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178 public static int encodeBlobCopy(PositionedByteRange dst, byte[] val, Order ord) {
1179 return encodeBlobCopy(dst, val, 0, null != val ? val.length : 0, ord);
1180 }
1181
1182
1183
1184
1185
1186 public static byte[] decodeBlobCopy(PositionedByteRange src) {
1187 byte header = src.get();
1188 if (header == NULL || header == DESCENDING.apply(NULL)) {
1189 return null;
1190 }
1191 assert header == BLOB_COPY || header == DESCENDING.apply(BLOB_COPY);
1192 Order ord = header == BLOB_COPY ? ASCENDING : DESCENDING;
1193 final int length = src.getRemaining() - (ASCENDING == ord ? 0 : 1);
1194 byte[] ret = new byte[length];
1195 src.get(ret);
1196 ord.apply(ret, 0, ret.length);
1197
1198
1199 if (DESCENDING == ord) src.get();
1200 return ret;
1201 }
1202
1203
1204
1205
1206
1207
1208
1209 public static int encodeNull(PositionedByteRange dst, Order ord) {
1210 dst.put(ord.apply(NULL));
1211 return 1;
1212 }
1213
1214
1215
1216
1217
1218
1219
1220 public static int encodeInt8(PositionedByteRange dst, byte val, Order ord) {
1221 final int offset = dst.getOffset(), start = dst.getPosition();
1222 dst.put(FIXED_INT8)
1223 .put((byte) (val ^ 0x80));
1224 ord.apply(dst.getBytes(), offset + start, 2);
1225 return 2;
1226 }
1227
1228
1229
1230
1231
1232 public static byte decodeInt8(PositionedByteRange src) {
1233 final byte header = src.get();
1234 assert header == FIXED_INT8 || header == DESCENDING.apply(FIXED_INT8);
1235 Order ord = header == FIXED_INT8 ? ASCENDING : DESCENDING;
1236 return (byte)((ord.apply(src.get()) ^ 0x80) & 0xff);
1237 }
1238
1239
1240
1241
1242
1243
1244
1245 public static int encodeInt16(PositionedByteRange dst, short val, Order ord) {
1246 final int offset = dst.getOffset(), start = dst.getPosition();
1247 dst.put(FIXED_INT16)
1248 .put((byte) ((val >> 8) ^ 0x80))
1249 .put((byte) val);
1250 ord.apply(dst.getBytes(), offset + start, 3);
1251 return 3;
1252 }
1253
1254
1255
1256
1257
1258 public static short decodeInt16(PositionedByteRange src) {
1259 final byte header = src.get();
1260 assert header == FIXED_INT16 || header == DESCENDING.apply(FIXED_INT16);
1261 Order ord = header == FIXED_INT16 ? ASCENDING : DESCENDING;
1262 short val = (short) ((ord.apply(src.get()) ^ 0x80) & 0xff);
1263 val = (short) ((val << 8) + (ord.apply(src.get()) & 0xff));
1264 return val;
1265 }
1266
1267
1268
1269
1270
1271
1272
1273 public static int encodeInt32(PositionedByteRange dst, int val, Order ord) {
1274 final int offset = dst.getOffset(), start = dst.getPosition();
1275 dst.put(FIXED_INT32)
1276 .put((byte) ((val >> 24) ^ 0x80))
1277 .put((byte) (val >> 16))
1278 .put((byte) (val >> 8))
1279 .put((byte) val);
1280 ord.apply(dst.getBytes(), offset + start, 5);
1281 return 5;
1282 }
1283
1284
1285
1286
1287
1288 public static int decodeInt32(PositionedByteRange src) {
1289 final byte header = src.get();
1290 assert header == FIXED_INT32 || header == DESCENDING.apply(FIXED_INT32);
1291 Order ord = header == FIXED_INT32 ? ASCENDING : DESCENDING;
1292 int val = (ord.apply(src.get()) ^ 0x80) & 0xff;
1293 for (int i = 1; i < 4; i++) {
1294 val = (val << 8) + (ord.apply(src.get()) & 0xff);
1295 }
1296 return val;
1297 }
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336 public static int encodeInt64(PositionedByteRange dst, long val, Order ord) {
1337 final int offset = dst.getOffset(), start = dst.getPosition();
1338 dst.put(FIXED_INT64)
1339 .put((byte) ((val >> 56) ^ 0x80))
1340 .put((byte) (val >> 48))
1341 .put((byte) (val >> 40))
1342 .put((byte) (val >> 32))
1343 .put((byte) (val >> 24))
1344 .put((byte) (val >> 16))
1345 .put((byte) (val >> 8))
1346 .put((byte) val);
1347 ord.apply(dst.getBytes(), offset + start, 9);
1348 return 9;
1349 }
1350
1351
1352
1353
1354
1355 public static long decodeInt64(PositionedByteRange src) {
1356 final byte header = src.get();
1357 assert header == FIXED_INT64 || header == DESCENDING.apply(FIXED_INT64);
1358 Order ord = header == FIXED_INT64 ? ASCENDING : DESCENDING;
1359 long val = (ord.apply(src.get()) ^ 0x80) & 0xff;
1360 for (int i = 1; i < 8; i++) {
1361 val = (val << 8) + (ord.apply(src.get()) & 0xff);
1362 }
1363 return val;
1364 }
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374 public static int encodeFloat32(PositionedByteRange dst, float val, Order ord) {
1375 final int offset = dst.getOffset(), start = dst.getPosition();
1376 int i = Float.floatToIntBits(val);
1377 i ^= ((i >> Integer.SIZE - 1) | Integer.MIN_VALUE);
1378 dst.put(FIXED_FLOAT32)
1379 .put((byte) (i >> 24))
1380 .put((byte) (i >> 16))
1381 .put((byte) (i >> 8))
1382 .put((byte) i);
1383 ord.apply(dst.getBytes(), offset + start, 5);
1384 return 5;
1385 }
1386
1387
1388
1389
1390
1391 public static float decodeFloat32(PositionedByteRange src) {
1392 final byte header = src.get();
1393 assert header == FIXED_FLOAT32 || header == DESCENDING.apply(FIXED_FLOAT32);
1394 Order ord = header == FIXED_FLOAT32 ? ASCENDING : DESCENDING;
1395 int val = ord.apply(src.get()) & 0xff;
1396 for (int i = 1; i < 4; i++) {
1397 val = (val << 8) + (ord.apply(src.get()) & 0xff);
1398 }
1399 val ^= (~val >> Integer.SIZE - 1) | Integer.MIN_VALUE;
1400 return Float.intBitsToFloat(val);
1401 }
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468 public static int encodeFloat64(PositionedByteRange dst, double val, Order ord) {
1469 final int offset = dst.getOffset(), start = dst.getPosition();
1470 long lng = Double.doubleToLongBits(val);
1471 lng ^= ((lng >> Long.SIZE - 1) | Long.MIN_VALUE);
1472 dst.put(FIXED_FLOAT64)
1473 .put((byte) (lng >> 56))
1474 .put((byte) (lng >> 48))
1475 .put((byte) (lng >> 40))
1476 .put((byte) (lng >> 32))
1477 .put((byte) (lng >> 24))
1478 .put((byte) (lng >> 16))
1479 .put((byte) (lng >> 8))
1480 .put((byte) lng);
1481 ord.apply(dst.getBytes(), offset + start, 9);
1482 return 9;
1483 }
1484
1485
1486
1487
1488
1489 public static double decodeFloat64(PositionedByteRange src) {
1490 final byte header = src.get();
1491 assert header == FIXED_FLOAT64 || header == DESCENDING.apply(FIXED_FLOAT64);
1492 Order ord = header == FIXED_FLOAT64 ? ASCENDING : DESCENDING;
1493 long val = ord.apply(src.get()) & 0xff;
1494 for (int i = 1; i < 8; i++) {
1495 val = (val << 8) + (ord.apply(src.get()) & 0xff);
1496 }
1497 val ^= (~val >> Long.SIZE - 1) | Long.MIN_VALUE;
1498 return Double.longBitsToDouble(val);
1499 }
1500
1501
1502
1503
1504
1505 public static boolean isEncodedValue(PositionedByteRange src) {
1506 return isNull(src) || isNumeric(src) || isFixedInt8(src) || isFixedInt16(src)
1507 || isFixedInt32(src) || isFixedInt64(src)
1508 || isFixedFloat32(src) || isFixedFloat64(src) || isText(src) || isBlobCopy(src)
1509 || isBlobVar(src);
1510 }
1511
1512
1513
1514
1515
1516 public static boolean isNull(PositionedByteRange src) {
1517 return NULL ==
1518 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1519 }
1520
1521
1522
1523
1524
1525
1526 public static boolean isNumeric(PositionedByteRange src) {
1527 byte x = (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1528 return x >= NEG_INF && x <= NAN;
1529 }
1530
1531
1532
1533
1534
1535 public static boolean isNumericInfinite(PositionedByteRange src) {
1536 byte x = (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1537 return NEG_INF == x || POS_INF == x;
1538 }
1539
1540
1541
1542
1543
1544 public static boolean isNumericNaN(PositionedByteRange src) {
1545 return NAN == (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1546 }
1547
1548
1549
1550
1551
1552 public static boolean isNumericZero(PositionedByteRange src) {
1553 return ZERO ==
1554 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1555 }
1556
1557
1558
1559
1560
1561 public static boolean isFixedInt8(PositionedByteRange src) {
1562 return FIXED_INT8 ==
1563 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1564 }
1565
1566
1567
1568
1569
1570 public static boolean isFixedInt16(PositionedByteRange src) {
1571 return FIXED_INT16 ==
1572 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1573 }
1574
1575
1576
1577
1578
1579 public static boolean isFixedInt32(PositionedByteRange src) {
1580 return FIXED_INT32 ==
1581 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1582 }
1583
1584
1585
1586
1587
1588 public static boolean isFixedInt64(PositionedByteRange src) {
1589 return FIXED_INT64 ==
1590 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1591 }
1592
1593
1594
1595
1596
1597 public static boolean isFixedFloat32(PositionedByteRange src) {
1598 return FIXED_FLOAT32 ==
1599 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1600 }
1601
1602
1603
1604
1605
1606 public static boolean isFixedFloat64(PositionedByteRange src) {
1607 return FIXED_FLOAT64 ==
1608 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1609 }
1610
1611
1612
1613
1614
1615 public static boolean isText(PositionedByteRange src) {
1616 return TEXT ==
1617 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1618 }
1619
1620
1621
1622
1623
1624 public static boolean isBlobVar(PositionedByteRange src) {
1625 return BLOB_VAR ==
1626 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1627 }
1628
1629
1630
1631
1632
1633 public static boolean isBlobCopy(PositionedByteRange src) {
1634 return BLOB_COPY ==
1635 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1636 }
1637
1638
1639
1640
1641
1642 public static int skip(PositionedByteRange src) {
1643 final int start = src.getPosition();
1644 byte header = src.get();
1645 Order ord = (-1 == Integer.signum(header)) ? DESCENDING : ASCENDING;
1646 header = ord.apply(header);
1647
1648 switch (header) {
1649 case NULL:
1650 case NEG_INF:
1651 return 1;
1652 case NEG_LARGE:
1653 skipVaruint64(src, DESCENDING != ord);
1654 skipSignificand(src, DESCENDING != ord);
1655 return src.getPosition() - start;
1656 case NEG_MED_MIN:
1657 case NEG_MED_MIN + 0x01:
1658 case NEG_MED_MIN + 0x02:
1659 case NEG_MED_MIN + 0x03:
1660 case NEG_MED_MIN + 0x04:
1661 case NEG_MED_MIN + 0x05:
1662 case NEG_MED_MIN + 0x06:
1663 case NEG_MED_MIN + 0x07:
1664 case NEG_MED_MIN + 0x08:
1665 case NEG_MED_MIN + 0x09:
1666 case NEG_MED_MAX:
1667 skipSignificand(src, DESCENDING != ord);
1668 return src.getPosition() - start;
1669 case NEG_SMALL:
1670 skipVaruint64(src, DESCENDING == ord);
1671 skipSignificand(src, DESCENDING != ord);
1672 return src.getPosition() - start;
1673 case ZERO:
1674 return 1;
1675 case POS_SMALL:
1676 skipVaruint64(src, DESCENDING != ord);
1677 skipSignificand(src, DESCENDING == ord);
1678 return src.getPosition() - start;
1679 case POS_MED_MIN:
1680 case POS_MED_MIN + 0x01:
1681 case POS_MED_MIN + 0x02:
1682 case POS_MED_MIN + 0x03:
1683 case POS_MED_MIN + 0x04:
1684 case POS_MED_MIN + 0x05:
1685 case POS_MED_MIN + 0x06:
1686 case POS_MED_MIN + 0x07:
1687 case POS_MED_MIN + 0x08:
1688 case POS_MED_MIN + 0x09:
1689 case POS_MED_MAX:
1690 skipSignificand(src, DESCENDING == ord);
1691 return src.getPosition() - start;
1692 case POS_LARGE:
1693 skipVaruint64(src, DESCENDING == ord);
1694 skipSignificand(src, DESCENDING == ord);
1695 return src.getPosition() - start;
1696 case POS_INF:
1697 return 1;
1698 case NAN:
1699 return 1;
1700 case FIXED_INT8:
1701 src.setPosition(src.getPosition() + 1);
1702 return src.getPosition() - start;
1703 case FIXED_INT16:
1704 src.setPosition(src.getPosition() + 2);
1705 return src.getPosition() - start;
1706 case FIXED_INT32:
1707 src.setPosition(src.getPosition() + 4);
1708 return src.getPosition() - start;
1709 case FIXED_INT64:
1710 src.setPosition(src.getPosition() + 8);
1711 return src.getPosition() - start;
1712 case FIXED_FLOAT32:
1713 src.setPosition(src.getPosition() + 4);
1714 return src.getPosition() - start;
1715 case FIXED_FLOAT64:
1716 src.setPosition(src.getPosition() + 8);
1717 return src.getPosition() - start;
1718 case TEXT:
1719
1720 do {
1721 header = ord.apply(src.get());
1722 } while (header != TERM);
1723 return src.getPosition() - start;
1724 case BLOB_VAR:
1725
1726 do {
1727 header = ord.apply(src.get());
1728 } while ((byte) (header & 0x80) != TERM);
1729 return src.getPosition() - start;
1730 case BLOB_COPY:
1731 if (Order.DESCENDING == ord) {
1732
1733 do {
1734 header = ord.apply(src.get());
1735 } while (header != TERM);
1736 return src.getPosition() - start;
1737 } else {
1738
1739 src.setPosition(src.getLength());
1740 return src.getPosition() - start;
1741 }
1742 default:
1743 throw unexpectedHeader(header);
1744 }
1745 }
1746
1747
1748
1749
1750
1751 public static int length(PositionedByteRange buff) {
1752 PositionedByteRange b =
1753 new SimplePositionedMutableByteRange(buff.getBytes(), buff.getOffset(), buff.getLength());
1754 b.setPosition(buff.getPosition());
1755 int cnt = 0;
1756 for (; isEncodedValue(b); skip(b), cnt++)
1757 ;
1758 return cnt;
1759 }
1760 }