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 import java.util.Comparator;
29
30 import org.apache.hadoop.hbase.classification.InterfaceAudience;
31 import org.apache.hadoop.hbase.classification.InterfaceStability;
32
33 import com.google.common.annotations.VisibleForTesting;
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
270 @InterfaceAudience.Public
271 @InterfaceStability.Evolving
272 public class OrderedBytes {
273
274
275
276
277
278
279
280
281
282 private static final byte NULL = 0x05;
283
284 private static final byte NEG_INF = 0x07;
285 private static final byte NEG_LARGE = 0x08;
286 private static final byte NEG_MED_MIN = 0x09;
287 private static final byte NEG_MED_MAX = 0x13;
288 private static final byte NEG_SMALL = 0x14;
289 private static final byte ZERO = 0x15;
290 private static final byte POS_SMALL = 0x16;
291 private static final byte POS_MED_MIN = 0x17;
292 private static final byte POS_MED_MAX = 0x21;
293 private static final byte POS_LARGE = 0x22;
294 private static final byte POS_INF = 0x23;
295
296 private static final byte NAN = 0x26;
297
298 private static final byte FIXED_INT8 = 0x29;
299 private static final byte FIXED_INT16 = 0x2a;
300 private static final byte FIXED_INT32 = 0x2b;
301 private static final byte FIXED_INT64 = 0x2c;
302
303 private static final byte FIXED_FLOAT32 = 0x30;
304 private static final byte FIXED_FLOAT64 = 0x31;
305
306 private static final byte TEXT = 0x34;
307
308 private static final byte BLOB_VAR = 0x37;
309 private static final byte BLOB_COPY = 0x38;
310
311
312
313
314
315 public static final Charset UTF8 = Charset.forName("UTF-8");
316 private static final byte TERM = 0x00;
317 private static final BigDecimal E8 = BigDecimal.valueOf(1e8);
318 private static final BigDecimal E32 = BigDecimal.valueOf(1e32);
319 private static final BigDecimal EN2 = BigDecimal.valueOf(1e-2);
320 private static final BigDecimal EN10 = BigDecimal.valueOf(1e-10);
321
322
323
324
325 public static final int MAX_PRECISION = 31;
326
327
328
329
330 public static final MathContext DEFAULT_MATH_CONTEXT =
331 new MathContext(MAX_PRECISION, RoundingMode.HALF_UP);
332
333
334
335
336
337
338 private static IllegalArgumentException unexpectedHeader(byte header) {
339 throw new IllegalArgumentException("unexpected value in first byte: 0x"
340 + Long.toHexString(header));
341 }
342
343
344
345
346
347 private static int unsignedCmp(long x1, long x2) {
348 int cmp;
349 if ((cmp = (x1 < x2 ? -1 : (x1 == x2 ? 0 : 1))) == 0) return 0;
350
351 if ((x1 < 0) != (x2 < 0)) return -cmp;
352 return cmp;
353 }
354
355
356
357
358
359 private static int putUint32(PositionedByteRange dst, int val) {
360 dst.put((byte) (val >>> 24))
361 .put((byte) (val >>> 16))
362 .put((byte) (val >>> 8))
363 .put((byte) val);
364 return 4;
365 }
366
367
368
369
370
371
372
373
374 @VisibleForTesting
375 static int putVaruint64(PositionedByteRange dst, long val, boolean comp) {
376 int w, y, len = 0;
377 final int offset = dst.getOffset(), start = dst.getPosition();
378 byte[] a = dst.getBytes();
379 Order ord = comp ? DESCENDING : ASCENDING;
380 if (-1 == unsignedCmp(val, 241L)) {
381 dst.put((byte) val);
382 len = dst.getPosition() - start;
383 ord.apply(a, offset + start, len);
384 return len;
385 }
386 if (-1 == unsignedCmp(val, 2288L)) {
387 y = (int) (val - 240);
388 dst.put((byte) (y / 256 + 241))
389 .put((byte) (y % 256));
390 len = dst.getPosition() - start;
391 ord.apply(a, offset + start, len);
392 return len;
393 }
394 if (-1 == unsignedCmp(val, 67824L)) {
395 y = (int) (val - 2288);
396 dst.put((byte) 249)
397 .put((byte) (y / 256))
398 .put((byte) (y % 256));
399 len = dst.getPosition() - start;
400 ord.apply(a, offset + start, len);
401 return len;
402 }
403 y = (int) val;
404 w = (int) (val >>> 32);
405 if (w == 0) {
406 if (-1 == unsignedCmp(y, 16777216L)) {
407 dst.put((byte) 250)
408 .put((byte) (y >>> 16))
409 .put((byte) (y >>> 8))
410 .put((byte) y);
411 len = dst.getPosition() - start;
412 ord.apply(a, offset + start, len);
413 return len;
414 }
415 dst.put((byte) 251);
416 putUint32(dst, y);
417 len = dst.getPosition() - start;
418 ord.apply(a, offset + start, len);
419 return len;
420 }
421 if (-1 == unsignedCmp(w, 256L)) {
422 dst.put((byte) 252)
423 .put((byte) w);
424 putUint32(dst, y);
425 len = dst.getPosition() - start;
426 ord.apply(a, offset + start, len);
427 return len;
428 }
429 if (-1 == unsignedCmp(w, 65536L)) {
430 dst.put((byte) 253)
431 .put((byte) (w >>> 8))
432 .put((byte) w);
433 putUint32(dst, y);
434 len = dst.getPosition() - start;
435 ord.apply(a, offset + start, len);
436 return len;
437 }
438 if (-1 == unsignedCmp(w, 16777216L)) {
439 dst.put((byte) 254)
440 .put((byte) (w >>> 16))
441 .put((byte) (w >>> 8))
442 .put((byte) w);
443 putUint32(dst, y);
444 len = dst.getPosition() - start;
445 ord.apply(a, offset + start, len);
446 return len;
447 }
448 dst.put((byte) 255);
449 putUint32(dst, w);
450 putUint32(dst, y);
451 len = dst.getPosition() - start;
452 ord.apply(a, offset + start, len);
453 return len;
454 }
455
456
457
458
459
460
461
462
463 @VisibleForTesting
464 static int lengthVaruint64(PositionedByteRange src, boolean comp) {
465 int a0 = (comp ? DESCENDING : ASCENDING).apply(src.peek()) & 0xff;
466 if (a0 <= 240) return 1;
467 if (a0 >= 241 && a0 <= 248) return 2;
468 if (a0 == 249) return 3;
469 if (a0 == 250) return 4;
470 if (a0 == 251) return 5;
471 if (a0 == 252) return 6;
472 if (a0 == 253) return 7;
473 if (a0 == 254) return 8;
474 if (a0 == 255) return 9;
475 throw unexpectedHeader(src.peek());
476 }
477
478
479
480
481
482
483
484 @VisibleForTesting
485 static int skipVaruint64(PositionedByteRange src, boolean cmp) {
486 final int len = lengthVaruint64(src, cmp);
487 src.setPosition(src.getPosition() + len);
488 return len;
489 }
490
491
492
493
494
495
496 @VisibleForTesting
497 static long getVaruint64(PositionedByteRange src, boolean comp) {
498 assert src.getRemaining() >= lengthVaruint64(src, comp);
499 final long ret;
500 Order ord = comp ? DESCENDING : ASCENDING;
501 byte x = src.get();
502 final int a0 = ord.apply(x) & 0xff, a1, a2, a3, a4, a5, a6, a7, a8;
503 if (-1 == unsignedCmp(a0, 241)) {
504 return a0;
505 }
506 x = src.get();
507 a1 = ord.apply(x) & 0xff;
508 if (-1 == unsignedCmp(a0, 249)) {
509 return (a0 - 241) * 256 + a1 + 240;
510 }
511 x = src.get();
512 a2 = ord.apply(x) & 0xff;
513 if (a0 == 249) {
514 return 2288 + 256 * a1 + a2;
515 }
516 x = src.get();
517 a3 = ord.apply(x) & 0xff;
518 if (a0 == 250) {
519 return (a1 << 16) | (a2 << 8) | a3;
520 }
521 x = src.get();
522 a4 = ord.apply(x) & 0xff;
523 ret = (((long) a1) << 24) | (a2 << 16) | (a3 << 8) | a4;
524 if (a0 == 251) {
525 return ret;
526 }
527 x = src.get();
528 a5 = ord.apply(x) & 0xff;
529 if (a0 == 252) {
530 return (ret << 8) | a5;
531 }
532 x = src.get();
533 a6 = ord.apply(x) & 0xff;
534 if (a0 == 253) {
535 return (ret << 16) | (a5 << 8) | a6;
536 }
537 x = src.get();
538 a7 = ord.apply(x) & 0xff;
539 if (a0 == 254) {
540 return (ret << 24) | (a5 << 16) | (a6 << 8) | a7;
541 }
542 x = src.get();
543 a8 = ord.apply(x) & 0xff;
544 return (ret << 32) | (((long) a5) << 24) | (a6 << 16) | (a7 << 8) | a8;
545 }
546
547
548
549
550
551
552
553 @VisibleForTesting
554 static BigDecimal normalize(BigDecimal val) {
555 return null == val ? null : val.stripTrailingZeros().round(DEFAULT_MATH_CONTEXT);
556 }
557
558
559
560
561
562
563
564
565
566
567
568 private static BigDecimal decodeSignificand(PositionedByteRange src, int e, boolean comp) {
569
570 byte[] a = src.getBytes();
571 final int start = src.getPosition(), offset = src.getOffset(), remaining = src.getRemaining();
572 Order ord = comp ? DESCENDING : ASCENDING;
573 BigDecimal m = BigDecimal.ZERO;
574 e--;
575 for (int i = 0;; i++) {
576 if (i > remaining) {
577
578 src.setPosition(start);
579 throw new IllegalArgumentException(
580 "Read exceeds range before termination byte found. offset: " + offset + " position: "
581 + (start + i));
582 }
583
584 m = m.add(
585 new BigDecimal(BigInteger.ONE, e * -2).multiply(
586 BigDecimal.valueOf((ord.apply(a[offset + start + i]) & 0xff) / 2)));
587 e--;
588
589 if ((ord.apply(a[offset + start + i]) & 1) == 0) {
590 src.setPosition(start + i + 1);
591 break;
592 }
593 }
594 return normalize(m);
595 }
596
597
598
599
600
601
602
603 private static int skipSignificand(PositionedByteRange src, boolean comp) {
604 byte[] a = src.getBytes();
605 final int offset = src.getOffset(), start = src.getPosition();
606 int i = src.getPosition();
607 while (((comp ? DESCENDING : ASCENDING).apply(a[offset + i++]) & 1) != 0)
608 ;
609 src.setPosition(i);
610 return i - start;
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
637 private static int encodeNumericSmall(PositionedByteRange dst, BigDecimal val) {
638
639
640 BigDecimal abs = val.abs();
641 assert BigDecimal.ZERO.compareTo(abs) < 0 && BigDecimal.ONE.compareTo(abs) > 0;
642 byte[] a = dst.getBytes();
643 boolean isNeg = val.signum() == -1;
644 final int offset = dst.getOffset(), start = dst.getPosition();
645 int e = 0, d, startM;
646
647 if (isNeg) {
648 dst.put(NEG_SMALL);
649 } else {
650 dst.put(POS_SMALL);
651 }
652
653
654 while (abs.compareTo(EN10) < 0) { abs = abs.movePointRight(8); e += 4; }
655 while (abs.compareTo(EN2) < 0) { abs = abs.movePointRight(2); e++; }
656
657 putVaruint64(dst, e, !isNeg);
658
659
660 startM = dst.getPosition();
661
662
663 for (int i = 0; i < 18 && abs.compareTo(BigDecimal.ZERO) != 0; i++) {
664 abs = abs.movePointRight(2);
665 d = abs.intValue();
666 dst.put((byte) ((2 * d + 1) & 0xff));
667 abs = abs.subtract(BigDecimal.valueOf(d));
668 }
669 a[offset + dst.getPosition() - 1] &= 0xfe;
670 if (isNeg) {
671
672 DESCENDING.apply(a, offset + startM, dst.getPosition() - startM);
673 }
674 return dst.getPosition() - start;
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
713 private static int encodeNumericLarge(PositionedByteRange dst, BigDecimal val) {
714
715 BigDecimal abs = val.abs();
716 byte[] a = dst.getBytes();
717 boolean isNeg = val.signum() == -1;
718 final int start = dst.getPosition(), offset = dst.getOffset();
719 int e = 0, d, startM;
720
721 if (isNeg) {
722 dst.put(NEG_LARGE);
723 } else {
724 dst.put(POS_LARGE);
725 }
726
727
728 while (abs.compareTo(E32) >= 0 && e <= 350) { abs = abs.movePointLeft(32); e +=16; }
729 while (abs.compareTo(E8) >= 0 && e <= 350) { abs = abs.movePointLeft(8); e+= 4; }
730 while (abs.compareTo(BigDecimal.ONE) >= 0 && e <= 350) { abs = abs.movePointLeft(2); e++; }
731
732
733 if (e > 10) {
734 putVaruint64(dst, e, isNeg);
735 } else {
736 if (isNeg) {
737 dst.put(start, (byte) (NEG_MED_MAX - e));
738 } else {
739 dst.put(start, (byte) (POS_MED_MIN + e));
740 }
741 }
742
743
744 startM = dst.getPosition();
745
746
747 for (int i = 0; i < 18 && abs.compareTo(BigDecimal.ZERO) != 0; i++) {
748 abs = abs.movePointRight(2);
749 d = abs.intValue();
750 dst.put((byte) (2 * d + 1));
751 abs = abs.subtract(BigDecimal.valueOf(d));
752 }
753
754 a[offset + dst.getPosition() - 1] &= 0xfe;
755 if (isNeg) {
756
757 DESCENDING.apply(a, offset + startM, dst.getPosition() - startM);
758 }
759 return dst.getPosition() - start;
760 }
761
762
763
764
765
766
767
768
769 public static int encodeNumeric(PositionedByteRange dst, long val, Order ord) {
770 return encodeNumeric(dst, BigDecimal.valueOf(val), ord);
771 }
772
773
774
775
776
777
778
779
780 public static int encodeNumeric(PositionedByteRange dst, double val, Order ord) {
781 if (val == 0.0) {
782 dst.put(ord.apply(ZERO));
783 return 1;
784 }
785 if (Double.isNaN(val)) {
786 dst.put(ord.apply(NAN));
787 return 1;
788 }
789 if (val == Double.NEGATIVE_INFINITY) {
790 dst.put(ord.apply(NEG_INF));
791 return 1;
792 }
793 if (val == Double.POSITIVE_INFINITY) {
794 dst.put(ord.apply(POS_INF));
795 return 1;
796 }
797 return encodeNumeric(dst, BigDecimal.valueOf(val), ord);
798 }
799
800
801
802
803
804
805
806
807 public static int encodeNumeric(PositionedByteRange dst, BigDecimal val, Order ord) {
808 final int len, offset = dst.getOffset(), start = dst.getPosition();
809 if (null == val) {
810 return encodeNull(dst, ord);
811 } else if (BigDecimal.ZERO.compareTo(val) == 0) {
812 dst.put(ord.apply(ZERO));
813 return 1;
814 }
815 BigDecimal abs = val.abs();
816 if (BigDecimal.ONE.compareTo(abs) <= 0) {
817 len = encodeNumericLarge(dst, normalize(val));
818 } else {
819 len = encodeNumericSmall(dst, normalize(val));
820 }
821 ord.apply(dst.getBytes(), offset + start, len);
822 return len;
823 }
824
825
826
827
828
829
830
831
832 private static BigDecimal decodeNumericValue(PositionedByteRange src) {
833 final int e;
834 byte header = src.get();
835 boolean dsc = -1 == Integer.signum(header);
836 header = dsc ? DESCENDING.apply(header) : header;
837
838 if (header == NULL) return null;
839 if (header == NEG_LARGE) {
840 e = (int) getVaruint64(src, !dsc);
841 return decodeSignificand(src, e, !dsc).negate();
842 }
843 if (header >= NEG_MED_MIN && header <= NEG_MED_MAX) {
844
845 e = NEG_MED_MAX - header;
846 return decodeSignificand(src, e, !dsc).negate();
847 }
848 if (header == NEG_SMALL) {
849 e = (int) -getVaruint64(src, dsc);
850 return decodeSignificand(src, e, !dsc).negate();
851 }
852 if (header == ZERO) {
853 return BigDecimal.ZERO;
854 }
855 if (header == POS_SMALL) {
856 e = (int) -getVaruint64(src, !dsc);
857 return decodeSignificand(src, e, dsc);
858 }
859 if (header >= POS_MED_MIN && header <= POS_MED_MAX) {
860
861 e = header - POS_MED_MIN;
862 return decodeSignificand(src, e, dsc);
863 }
864 if (header == POS_LARGE) {
865 e = (int) getVaruint64(src, dsc);
866 return decodeSignificand(src, e, dsc);
867 }
868 throw unexpectedHeader(header);
869 }
870
871
872
873
874
875
876
877
878
879
880
881
882 public static double decodeNumericAsDouble(PositionedByteRange src) {
883
884 if (isNull(src)) {
885 throw new NullPointerException("A null value cannot be decoded to a double.");
886 }
887 if (isNumericNaN(src)) {
888 src.get();
889 return Double.NaN;
890 }
891 if (isNumericZero(src)) {
892 src.get();
893 return Double.valueOf(0.0);
894 }
895
896 byte header = -1 == Integer.signum(src.peek()) ? DESCENDING.apply(src.peek()) : src.peek();
897
898 if (header == NEG_INF) {
899 src.get();
900 return Double.NEGATIVE_INFINITY;
901 } else if (header == POS_INF) {
902 src.get();
903 return Double.POSITIVE_INFINITY;
904 } else {
905 return decodeNumericValue(src).doubleValue();
906 }
907 }
908
909
910
911
912
913
914
915
916
917
918
919
920 public static long decodeNumericAsLong(PositionedByteRange src) {
921
922 if (isNull(src)) throw new NullPointerException();
923 if (!isNumeric(src)) throw unexpectedHeader(src.peek());
924 if (isNumericNaN(src)) throw unexpectedHeader(src.peek());
925 if (isNumericInfinite(src)) throw unexpectedHeader(src.peek());
926
927 if (isNumericZero(src)) {
928 src.get();
929 return Long.valueOf(0);
930 }
931 return decodeNumericValue(src).longValue();
932 }
933
934
935
936
937
938
939 public static BigDecimal decodeNumericAsBigDecimal(PositionedByteRange src) {
940 if (isNull(src)) {
941 src.get();
942 return null;
943 }
944 if (!isNumeric(src)) throw unexpectedHeader(src.peek());
945 if (isNumericNaN(src)) throw unexpectedHeader(src.peek());
946 if (isNumericInfinite(src)) throw unexpectedHeader(src.peek());
947 return decodeNumericValue(src);
948 }
949
950
951
952
953
954
955
956
957
958
959 public static int encodeString(PositionedByteRange dst, String val, Order ord) {
960 if (null == val) {
961 return encodeNull(dst, ord);
962 }
963 if (val.contains("\u0000"))
964 throw new IllegalArgumentException("Cannot encode String values containing '\\u0000'");
965 final int offset = dst.getOffset(), start = dst.getPosition();
966 dst.put(TEXT);
967
968 dst.put(val.getBytes(UTF8));
969 dst.put(TERM);
970 ord.apply(dst.getBytes(), offset + start, dst.getPosition() - start);
971 return dst.getPosition() - start;
972 }
973
974
975
976
977 public static String decodeString(PositionedByteRange src) {
978 final byte header = src.get();
979 if (header == NULL || header == DESCENDING.apply(NULL))
980 return null;
981 assert header == TEXT || header == DESCENDING.apply(TEXT);
982 Order ord = header == TEXT ? ASCENDING : DESCENDING;
983 byte[] a = src.getBytes();
984 final int offset = src.getOffset(), start = src.getPosition();
985 final byte terminator = ord.apply(TERM);
986 int rawStartPos = offset + start, rawTermPos = rawStartPos;
987 for (; a[rawTermPos] != terminator; rawTermPos++)
988 ;
989 src.setPosition(rawTermPos - offset + 1);
990 if (DESCENDING == ord) {
991
992 byte[] copy = new byte[rawTermPos - rawStartPos];
993 System.arraycopy(a, rawStartPos, copy, 0, copy.length);
994 ord.apply(copy);
995 return new String(copy, UTF8);
996 } else {
997 return new String(a, rawStartPos, rawTermPos - rawStartPos, UTF8);
998 }
999 }
1000
1001
1002
1003
1004 public static int blobVarEncodedLength(int len) {
1005 if (0 == len)
1006 return 2;
1007 else
1008 return (int)
1009 Math.ceil(
1010 (len * 8)
1011 / 7.0)
1012 + 1;
1013 }
1014
1015
1016
1017
1018 @VisibleForTesting
1019 static int blobVarDecodedLength(int len) {
1020 return
1021 ((len
1022 - 1)
1023 * 7)
1024 / 8;
1025 }
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042 public static int encodeBlobVar(PositionedByteRange dst, byte[] val, int voff, int vlen,
1043 Order ord) {
1044 if (null == val) {
1045 return encodeNull(dst, ord);
1046 }
1047
1048 assert dst.getRemaining() >= blobVarEncodedLength(vlen) : "buffer overflow expected.";
1049 final int offset = dst.getOffset(), start = dst.getPosition();
1050 dst.put(BLOB_VAR);
1051 if (0 == vlen) {
1052 dst.put(TERM);
1053 } else {
1054 byte s = 1, t = 0;
1055 for (int i = voff; i < vlen; i++) {
1056 dst.put((byte) (0x80 | t | ((val[i] & 0xff) >>> s)));
1057 if (s < 7) {
1058 t = (byte) (val[i] << (7 - s));
1059 s++;
1060 } else {
1061 dst.put((byte) (0x80 | val[i]));
1062 s = 1;
1063 t = 0;
1064 }
1065 }
1066 if (s > 1) {
1067 dst.put((byte) (0x7f & t));
1068 } else {
1069 dst.getBytes()[offset + dst.getPosition() - 1] &= 0x7f;
1070 }
1071 }
1072 ord.apply(dst.getBytes(), offset + start, dst.getPosition() - start);
1073 return dst.getPosition() - start;
1074 }
1075
1076
1077
1078
1079
1080
1081 public static int encodeBlobVar(PositionedByteRange dst, byte[] val, Order ord) {
1082 return encodeBlobVar(dst, val, 0, null != val ? val.length : 0, ord);
1083 }
1084
1085
1086
1087
1088 public static byte[] decodeBlobVar(PositionedByteRange src) {
1089 final byte header = src.get();
1090 if (header == NULL || header == DESCENDING.apply(NULL)) {
1091 return null;
1092 }
1093 assert header == BLOB_VAR || header == DESCENDING.apply(BLOB_VAR);
1094 Order ord = BLOB_VAR == header ? ASCENDING : DESCENDING;
1095 if (src.peek() == ord.apply(TERM)) {
1096
1097 src.get();
1098 return new byte[0];
1099 }
1100 final int offset = src.getOffset(), start = src.getPosition();
1101 int end;
1102 byte[] a = src.getBytes();
1103 for (end = start; (byte) (ord.apply(a[offset + end]) & 0x80) != TERM; end++)
1104 ;
1105 end++;
1106
1107 PositionedByteRange ret = new SimplePositionedByteRange(blobVarDecodedLength(end - start + 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 public static int encodeFloat64(PositionedByteRange dst, double val, Order ord) {
1468 final int offset = dst.getOffset(), start = dst.getPosition();
1469 long lng = Double.doubleToLongBits(val);
1470 lng ^= ((lng >> Long.SIZE - 1) | Long.MIN_VALUE);
1471 dst.put(FIXED_FLOAT64)
1472 .put((byte) (lng >> 56))
1473 .put((byte) (lng >> 48))
1474 .put((byte) (lng >> 40))
1475 .put((byte) (lng >> 32))
1476 .put((byte) (lng >> 24))
1477 .put((byte) (lng >> 16))
1478 .put((byte) (lng >> 8))
1479 .put((byte) lng);
1480 ord.apply(dst.getBytes(), offset + start, 9);
1481 return 9;
1482 }
1483
1484
1485
1486
1487
1488 public static double decodeFloat64(PositionedByteRange src) {
1489 final byte header = src.get();
1490 assert header == FIXED_FLOAT64 || header == DESCENDING.apply(FIXED_FLOAT64);
1491 Order ord = header == FIXED_FLOAT64 ? ASCENDING : DESCENDING;
1492 long val = ord.apply(src.get()) & 0xff;
1493 for (int i = 1; i < 8; i++) {
1494 val = (val << 8) + (ord.apply(src.get()) & 0xff);
1495 }
1496 val ^= (~val >> Long.SIZE - 1) | Long.MIN_VALUE;
1497 return Double.longBitsToDouble(val);
1498 }
1499
1500
1501
1502
1503
1504 public static boolean isEncodedValue(PositionedByteRange src) {
1505 return isNull(src) || isNumeric(src) || isFixedInt32(src) || isFixedInt64(src)
1506 || isFixedFloat32(src) || isFixedFloat64(src) || isText(src) || isBlobCopy(src)
1507 || isBlobVar(src);
1508 }
1509
1510
1511
1512
1513
1514 public static boolean isNull(PositionedByteRange src) {
1515 return NULL ==
1516 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1517 }
1518
1519
1520
1521
1522
1523
1524 public static boolean isNumeric(PositionedByteRange src) {
1525 byte x = (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1526 return x >= NEG_INF && x <= NAN;
1527 }
1528
1529
1530
1531
1532
1533 public static boolean isNumericInfinite(PositionedByteRange src) {
1534 byte x = (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1535 return NEG_INF == x || POS_INF == x;
1536 }
1537
1538
1539
1540
1541
1542 public static boolean isNumericNaN(PositionedByteRange src) {
1543 return NAN == (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1544 }
1545
1546
1547
1548
1549
1550 public static boolean isNumericZero(PositionedByteRange src) {
1551 return ZERO ==
1552 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1553 }
1554
1555
1556
1557
1558
1559 public static boolean isFixedInt32(PositionedByteRange src) {
1560 return FIXED_INT32 ==
1561 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1562 }
1563
1564
1565
1566
1567
1568 public static boolean isFixedInt64(PositionedByteRange src) {
1569 return FIXED_INT64 ==
1570 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1571 }
1572
1573
1574
1575
1576
1577 public static boolean isFixedFloat32(PositionedByteRange src) {
1578 return FIXED_FLOAT32 ==
1579 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1580 }
1581
1582
1583
1584
1585
1586 public static boolean isFixedFloat64(PositionedByteRange src) {
1587 return FIXED_FLOAT64 ==
1588 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1589 }
1590
1591
1592
1593
1594
1595 public static boolean isText(PositionedByteRange src) {
1596 return TEXT ==
1597 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1598 }
1599
1600
1601
1602
1603
1604 public static boolean isBlobVar(PositionedByteRange src) {
1605 return BLOB_VAR ==
1606 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1607 }
1608
1609
1610
1611
1612
1613 public static boolean isBlobCopy(PositionedByteRange src) {
1614 return BLOB_COPY ==
1615 (-1 == Integer.signum(src.peek()) ? DESCENDING : ASCENDING).apply(src.peek());
1616 }
1617
1618
1619
1620
1621
1622 public static int skip(PositionedByteRange src) {
1623 final int start = src.getPosition();
1624 byte header = src.get();
1625 Order ord = (-1 == Integer.signum(header)) ? DESCENDING : ASCENDING;
1626 header = ord.apply(header);
1627
1628 switch (header) {
1629 case NULL:
1630 case NEG_INF:
1631 return 1;
1632 case NEG_LARGE:
1633 skipVaruint64(src, DESCENDING != ord);
1634 skipSignificand(src, DESCENDING != ord);
1635 return src.getPosition() - start;
1636 case NEG_MED_MIN:
1637 case NEG_MED_MIN + 0x01:
1638 case NEG_MED_MIN + 0x02:
1639 case NEG_MED_MIN + 0x03:
1640 case NEG_MED_MIN + 0x04:
1641 case NEG_MED_MIN + 0x05:
1642 case NEG_MED_MIN + 0x06:
1643 case NEG_MED_MIN + 0x07:
1644 case NEG_MED_MIN + 0x08:
1645 case NEG_MED_MIN + 0x09:
1646 case NEG_MED_MAX:
1647 skipSignificand(src, DESCENDING != ord);
1648 return src.getPosition() - start;
1649 case NEG_SMALL:
1650 skipVaruint64(src, DESCENDING == ord);
1651 skipSignificand(src, DESCENDING != ord);
1652 return src.getPosition() - start;
1653 case ZERO:
1654 return 1;
1655 case POS_SMALL:
1656 skipVaruint64(src, DESCENDING != ord);
1657 skipSignificand(src, DESCENDING == ord);
1658 return src.getPosition() - start;
1659 case POS_MED_MIN:
1660 case POS_MED_MIN + 0x01:
1661 case POS_MED_MIN + 0x02:
1662 case POS_MED_MIN + 0x03:
1663 case POS_MED_MIN + 0x04:
1664 case POS_MED_MIN + 0x05:
1665 case POS_MED_MIN + 0x06:
1666 case POS_MED_MIN + 0x07:
1667 case POS_MED_MIN + 0x08:
1668 case POS_MED_MIN + 0x09:
1669 case POS_MED_MAX:
1670 skipSignificand(src, DESCENDING == ord);
1671 return src.getPosition() - start;
1672 case POS_LARGE:
1673 skipVaruint64(src, DESCENDING == ord);
1674 skipSignificand(src, DESCENDING == ord);
1675 return src.getPosition() - start;
1676 case POS_INF:
1677 return 1;
1678 case NAN:
1679 return 1;
1680 case FIXED_INT8:
1681 src.setPosition(src.getPosition() + 1);
1682 return src.getPosition() - start;
1683 case FIXED_INT16:
1684 src.setPosition(src.getPosition() + 2);
1685 return src.getPosition() - start;
1686 case FIXED_INT32:
1687 src.setPosition(src.getPosition() + 4);
1688 return src.getPosition() - start;
1689 case FIXED_INT64:
1690 src.setPosition(src.getPosition() + 8);
1691 return src.getPosition() - start;
1692 case FIXED_FLOAT32:
1693 src.setPosition(src.getPosition() + 4);
1694 return src.getPosition() - start;
1695 case FIXED_FLOAT64:
1696 src.setPosition(src.getPosition() + 8);
1697 return src.getPosition() - start;
1698 case TEXT:
1699
1700 do {
1701 header = ord.apply(src.get());
1702 } while (header != TERM);
1703 return src.getPosition() - start;
1704 case BLOB_VAR:
1705
1706 do {
1707 header = ord.apply(src.get());
1708 } while ((byte) (header & 0x80) != TERM);
1709 return src.getPosition() - start;
1710 case BLOB_COPY:
1711 if (Order.DESCENDING == ord) {
1712
1713 do {
1714 header = ord.apply(src.get());
1715 } while (header != TERM);
1716 return src.getPosition() - start;
1717 } else {
1718
1719 src.setPosition(src.getLength());
1720 return src.getPosition() - start;
1721 }
1722 default:
1723 throw unexpectedHeader(header);
1724 }
1725 }
1726
1727
1728
1729
1730
1731 public static int length(PositionedByteRange buff) {
1732 PositionedByteRange b =
1733 new SimplePositionedByteRange(buff.getBytes(), buff.getOffset(), buff.getLength());
1734 b.setPosition(buff.getPosition());
1735 int cnt = 0;
1736 for (; isEncodedValue(b); skip(buff), cnt++)
1737 ;
1738 return cnt;
1739 }
1740 }