aboutsummaryrefslogtreecommitdiffstats
path: root/src/com/google/common/io/protocol/ProtoBuf.java
blob: 2a2f8b7739f18aab6af76bf8319eae6929b32a74 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
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
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
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
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
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
1337
1338
1339
// Copyright 2007 The Android Open Source Project
// All Rights Reserved.

package com.google.common.io.protocol;

import java.io.*;
import java.util.*;

/**
 * Protocol buffer message object. Currently, it is assumed that tags ids are 
 * not large. This could be improved by storing a start offset, reducing the 
 * assumption to a dense number space.
 * <p>
 * ProtoBuf instances may or may not reference a ProtoBufType instance,
 * representing information from a corresponding .proto file, which defines tag 
 * data types. The type can only be set in the constructor, it cannot be 
 * changed later. 
 * <p>
 * If the type is null, the ProtoBuffer should be used only for reading or 
 * as a local persistent storage buffer. An untyped Protocol Buffer must never 
 * be sent to a server. 
 * <p>
 * If a ProtoBufType is set, unknown values are read from the stream and 
 * preserved, but it is not possible to add values for undefined tags using
 * this API. Attempts to set undefined tags will result in an exception.
 * <p>
 * This class provides two different sets of access methods for simple and
 * repeated tags. Simple access methods are has(tag), getXXX(tag), 
 * and setXXX(tag, value). Access methods for repeated tags are getCount(tag),
 * getXXX(tag, index), remove(tag, index), insert(tag, index, value) and 
 * addXXX(tag, value). Note that both sets of methods can be used in both cases,
 * but only the simple methods take default values into account. The reason for
 * this behavior is that default values cannot be removed -- they would reappear
 * after a serialization cycle. If a tag has repeated values, setXXX(tag, value)
 * will overwrite all of them and getXXX(tag) will throw an exception.
 *
 */

public class ProtoBuf {

  public static final Boolean FALSE = new Boolean(false);
  public static final Boolean TRUE = new Boolean(true);

  private static final String MSG_EOF = "Unexp.EOF";
  private static final String MSG_MISMATCH = "Type mismatch";
  private static final String MSG_UNSUPPORTED = "Unsupp.Type";

  // names copied from //net/proto2/internal/wire_format.cc
  static final int WIRETYPE_END_GROUP = 4;
  static final int WIRETYPE_FIXED32 = 5;
  static final int WIRETYPE_FIXED64 = 1;
  static final int WIRETYPE_LENGTH_DELIMITED = 2;
  static final int WIRETYPE_START_GROUP = 3;
  static final int WIRETYPE_VARINT = 0;

  /** Maximum number of bytes for VARINT wire format (64 bit, 7 bit/byte) */
  private static final int VARINT_MAX_BYTES = 10;
  
  private static Long[] SMALL_NUMBERS = {
      new Long(0), new Long(1), new Long(2), new Long(3), new Long(4),
      new Long(5), new Long(6), new Long(7), new Long(8), new Long(9),
      new Long(10), new Long(11), new Long(12), new Long(13), new Long(14),
      new Long(15)};

  private ProtoBufType msgType;
  private final Vector values = new Vector();
  
  /** 
   * Wire types picked up on the wire or implied by setters (if no other
   * type information is available.
   */
  private final StringBuffer wireTypes = new StringBuffer();

  /**
   * Creates a protocol message according to the given description. The
   * description is required if it is necessary to write the protocol buffer for
   * data exchange with other systems relying on the .proto file. 
   */
  public ProtoBuf(ProtoBufType type) {
    this.msgType = type;
  }

  /** 
   * Clears all data stored in this ProtoBuf.
   */
  public void clear() {
    values.setSize(0);
    wireTypes.setLength(0);
  }
  
  /**
   * Creates a new instance of the group with the given tag.
   */
  public ProtoBuf createGroup(int tag) {
    return new ProtoBuf((ProtoBufType) getType().getData(tag));
  }

  /**
   * Appends the given (repeated) tag with the given boolean value. 
   */
  public void addBool(int tag, boolean value){
    insertBool(tag, getCount(tag), value);
  }

  /**
   * Appends the given (repeated) tag with the given byte[] value.
   */
  public void addBytes(int tag, byte[] value){
    insertBytes(tag, getCount(tag), value);
  }

  /**
   * Appends the given (repeated) tag with the given int value.
   */
  public void addInt(int tag, int value){
    insertInt(tag, getCount(tag), value);
  }
  
  /**
   * Appends the given (repeated) tag with the given long value.
   */
  public void addLong(int tag, long value){
    insertLong(tag, getCount(tag), value);
  }

  /**
   * Appends the given (repeated) tag with the given float value.
   */
  public void addFloat(int tag, float value) {
    insertFloat(tag, getCount(tag), value);
  }

  /**
   * Appends the given (repeated) tag with the given double value.
   */
  public void addDouble(int tag, double value) {
    insertDouble(tag, getCount(tag), value);
  }

  /**
   * Appends the given (repeated) tag with the given group or message value.
   */
  public void addProtoBuf(int tag, ProtoBuf value){
    insertProtoBuf(tag, getCount(tag), value);
  }

  /**
   * Adds a new protobuf for the specified tag, setting the child protobuf's
   * type correctly for the tag.
   * @param tag the tag for which to create a new protobuf
   * @return the newly created protobuf
   */
  public ProtoBuf addNewProtoBuf(int tag) {
    ProtoBuf child = newProtoBufForTag(tag);
    addProtoBuf(tag, child);
    return child;
  }

  /**
   * Creates and returns a new protobuf for the specified tag, setting the new
   * protobuf's type correctly for the tag.
   * @param tag the tag for which to create a new protobuf
   * @return the newly created protobuf
   */
  public ProtoBuf newProtoBufForTag(int tag) {
      return new ProtoBuf((ProtoBufType) msgType.getData(tag));
  }

  /**
   * Appends the given (repeated) tag with the given String value.
   */
  public void addString(int tag, String value){
    insertString(tag, getCount(tag), value);
  }
  
  /** 
   * Returns the boolean value for the given tag.
   */
  public boolean getBool(int tag) {
    return ((Boolean) getObject(tag, ProtoBufType.TYPE_BOOL))
        .booleanValue();
  }

  /** 
   * Returns the boolean value for the given repeated tag at the given index. 
   */
  public boolean getBool(int tag, int index) {
    return ((Boolean) getObject(tag, index, ProtoBufType.TYPE_BOOL))
        .booleanValue();
  }

  /**
   * Returns the given string tag as byte array.
   */
  public byte[] getBytes(int tag) {
    return (byte[]) getObject(tag, ProtoBufType.TYPE_DATA);
  }

  /**
   * Returns the given repeated string tag at the given index as byte array.
   */
  public byte[] getBytes(int tag, int index) {
    return (byte[]) getObject(tag, index, ProtoBufType.TYPE_DATA);
  }

  /**
   * Returns the integer value for the given tag. 
   */
  public int getInt(int tag) {
    return (int) ((Long) getObject(tag, ProtoBufType.TYPE_INT32)).longValue();
  }

  /** 
   * Returns the integer value for the given repeated tag at the given index. 
   */
  public int getInt(int tag, int index) {
    return (int) ((Long) getObject(tag, index, 
        ProtoBufType.TYPE_INT32)).longValue();
  }

  /**
   * Returns the long value for the given tag. 
   */
  public long getLong(int tag) {
    return ((Long) getObject(tag, ProtoBufType.TYPE_INT64)).longValue();
  }

  /** 
   * Returns the long value for the given repeated tag at the given index. 
   */
  public long getLong(int tag, int index) {
    return ((Long) getObject(tag, index, ProtoBufType.TYPE_INT64)).longValue();
  }

  /**
   * Returns the float value for the given tag.
   */
  public float getFloat(int tag) {
    return Float.intBitsToFloat(getInt(tag));
  }

  /**
   * Returns the float value for the given repeated tag at the given index. 
   */
  public float getFloat(int tag, int index) {
    return Float.intBitsToFloat(getInt(tag, index));
  }

  /**
   * Returns the double value for the given tag.
   */
  public double getDouble(int tag) {
    return Double.longBitsToDouble(getLong(tag));
  }

  /**
   * Returns the double value for the given repeated tag at the given index. 
   */
  public double getDouble(int tag, int index) {
    return Double.longBitsToDouble(getLong(tag, index));
  }

  /**
   * Returns the group or nested message for the given tag.
   */
  public ProtoBuf getProtoBuf(int tag) {
    return (ProtoBuf) getObject(tag, ProtoBufType.TYPE_GROUP);
  }

  /**
   * Returns the group or nested message for the given repeated tag at the given
   * index.
   */
  public ProtoBuf getProtoBuf(int tag, int index) {
    return (ProtoBuf) getObject(tag, index, ProtoBufType.TYPE_GROUP);
  }

  /**
   * Returns the string value for a given tag converted to a Java String
   * assuming UTF-8 encoding.
   */
  public String getString(int tag) {
    return (String) getObject(tag, ProtoBufType.TYPE_TEXT);
  }

  /**
   * Returns the string value for a given repeated tag at the given index
   * converted to a Java String assuming UTF-8 encoding.
   */
  public String getString(int tag, int index) {
    return (String) getObject(tag, index, ProtoBufType.TYPE_TEXT);
  }

  /**
   * Returns the type definition of this protocol buffer or group -- if set. 
   */
  public ProtoBufType getType() {
    return msgType;
  }

  /**
   * Sets the type definition of this protocol buffer. Used internally in
   * ProtoBufUtil for incremental reading.
   * 
   * @param type the new type
   */
  void setType(ProtoBufType type) {
    if (values.size() != 0 || 
        (msgType != null && type != null && type != msgType)) {
      throw new IllegalArgumentException();
    }
    this.msgType = type;
  }
  
  /**
   * Convenience method for determining whether a tag has a value. Note: in 
   * contrast to getCount(tag) &gt; 0, this method takes the default value
   * into account.
   */
  public boolean has(int tag){
    return getCount(tag) > 0 || getDefault(tag) != null;
  }
  
  /**
   * Reads the contents of this ProtocolMessage from the given byte array.
   * Currently, this is a shortcut for parse(new ByteArrayInputStream(data)).
   * However, this may change in future versions for efficiency reasons.
   * 
   * @param data the byte array the ProtocolMessage is read from
   * @throws     IOException if an unexpected "End of file" is encountered in 
   *             the byte array
   */
  public ProtoBuf parse(byte[] data) throws IOException {
    parse(new ByteArrayInputStream(data), data.length);
    return this;
  }

  /**
   * Reads the contents of this ProtocolMessage from the given stream.
   * 
   * @param is the input stream providing the contents
   * @return   this
   * @throws   IOException raised if an IO exception occurs in the underlying
   *           stream or the end of the stream is reached at an unexpected
   *           position
   */
  
  public ProtoBuf parse(InputStream is) throws IOException {
    parse(is, Integer.MAX_VALUE);
    return this;
  }
  
  /**
   * Reads the contents of this ProtocolMessage from the given stream, consuming
   * at most the given number of bytes.
   * 
   * @param is        the input stream providing the contents
   * @param available maximum number of bytes to read
   * @return          this
   * @throws          IOException raised if an IO exception occurs in the 
   *                  underlying stream or the end of the stream is reached at 
   *                  an unexpected position
   */
  public int parse(InputStream is, int available) throws IOException {

    clear();
    while (available > 0) {
      long tagAndType = readVarInt(is, true /* permits EOF */);

      if (tagAndType == -1){
        break;
      }
      available -= getVarIntSize(tagAndType);
      int wireType = ((int) tagAndType) & 0x07;
      if (wireType == WIRETYPE_END_GROUP) {
        break;
      }
      int tag = (int) (tagAndType >>> 3);
      while (wireTypes.length() <= tag){
        wireTypes.append((char) ProtoBufType.TYPE_UNDEFINED);
      }
      wireTypes.setCharAt(tag, (char) wireType);

      // first step: decode tag value
      Object value;
      switch (wireType) {
        case WIRETYPE_VARINT:
          long v = readVarInt(is, false);
          available -= getVarIntSize(v);
          if (isZigZagEncodedType(tag)) {
            v = zigZagDecode(v);
          }
          value = (v >= 0 && v < SMALL_NUMBERS.length) ? 
              SMALL_NUMBERS[(int) v] : new Long(v);
          break;

        // also used for fixed values
        case WIRETYPE_FIXED32:
        case WIRETYPE_FIXED64:
          v = 0;
          int shift = 0;
          int count = (wireType == WIRETYPE_FIXED32) ? 4 : 8;
          available -= count;
          
          while (count-- > 0) {
            long l = is.read();
            v |= l << shift;
            shift += 8;
          }

          value = (v >= 0 && v < SMALL_NUMBERS.length) 
              ? SMALL_NUMBERS[(int) v]
              : new Long(v);
          break;

        case WIRETYPE_LENGTH_DELIMITED:
          int total = (int) readVarInt(is, false);
          available -= getVarIntSize(total);
          available -= total;
          
          if (getType(tag) == ProtoBufType.TYPE_MESSAGE) {
            ProtoBuf msg = new ProtoBuf((ProtoBufType) msgType.getData(tag));
            msg.parse(is, total);
            value = msg;
          } else {
            byte[] data = new byte[total];
            int pos = 0;
            while (pos < total) {
              count = is.read(data, pos, total - pos);
              if (count <= 0) {
                throw new IOException(MSG_EOF);
              }
              pos += count;
            }
            value = data;
          }
          break;

        case WIRETYPE_START_GROUP:
          ProtoBuf group = new ProtoBuf(msgType == null 
              ? null 
              : ((ProtoBufType) msgType.getData(tag)));
          available = group.parse(is, available);
          value = group;
          break;

        default:
          throw new RuntimeException(MSG_UNSUPPORTED + wireType);
      }
      insertObject(tag, getCount(tag), value);
    }
    
    if (available < 0){
      throw new IOException();
    }
    
    return available;
  }

  /**
   * Removes the tag value at the given index.
   */
  public void remove(int tag, int index){
    int count = getCount(tag);
    if (index >= count){
      throw new ArrayIndexOutOfBoundsException();
    }
    if (count == 1){
      values.setElementAt(null, tag);
    } else {
      Vector v = (Vector) values.elementAt(tag);
      v.removeElementAt(index);
    }
  }
  
  /**
   * Returns the number of repeated and optional (0..1) values for a given tag.
   * Note: Default values are not counted (and in general not considered in 
   * access methods for repeated tags), but considered for has(tag). 
   */
  public int getCount(int tag) {
    if (tag >= values.size()){
      return 0;
    }
    Object o = values.elementAt(tag);
    if (o == null){
      return 0;
    }
    return (o instanceof Vector) ? ((Vector) o).size() : 1;
  }

  /**
   * Returns the tag type of the given tag (one of the ProtoBufType.TYPE_XXX 
   * constants). If no ProtoBufType is set, the wire type is returned. If no
   * wire type is available, the wire type is determined by looking at the
   * tag value (making sure the wire type is consistent for all values). If
   * no value is set, TYPE_UNDEFINED is returned.
   */
  public int getType(int tag){
    int tagType = ProtoBufType.TYPE_UNDEFINED;
    if (msgType != null){
      tagType = msgType.getType(tag);
    }

    if (tagType == ProtoBufType.TYPE_UNDEFINED && tag < wireTypes.length()) {
      tagType = wireTypes.charAt(tag);
    }
    
    if (tagType == ProtoBufType.TYPE_UNDEFINED && getCount(tag) > 0) {
      Object o = getObject(tag, 0, ProtoBufType.TYPE_UNDEFINED);
      
      tagType = (o instanceof Long) || (o instanceof Boolean) 
        ? WIRETYPE_VARINT : WIRETYPE_LENGTH_DELIMITED;
    }
    
    return tagType;
  }
  
  /** 
   * Returns the number of bytes needed to store this protocol buffer 
   */
  public int getDataSize() {
    int size = 0;
    for (int tag = 0; tag <= maxTag(); tag++) {
      for (int i = 0; i < getCount(tag); i++) {
        size += getDataSize(tag, i);
      }
    }      
    return size;
  }
  
 
  /** 
   * Returns the size of the given value 
   */
  private int getDataSize(int tag, int i) {
    int tagSize = getVarIntSize(tag << 3);
    
    switch(getWireType(tag)){
      case WIRETYPE_FIXED32:
        return tagSize + 4;
      case WIRETYPE_FIXED64:
        return tagSize + 8;
      case WIRETYPE_VARINT:
        long value = getLong(tag, i);
        if (isZigZagEncodedType(tag)) {
          value = zigZagEncode(value);
        }
        return tagSize + getVarIntSize(value);
      case WIRETYPE_START_GROUP:
        // take end group into account....
        return tagSize + getProtoBuf(tag, i).getDataSize() + tagSize;
    }
    
    // take the object as stored
    Object o = getObject(tag, i, ProtoBufType.TYPE_UNDEFINED);
    
    int contentSize;
    
    if (o instanceof byte[]){
      contentSize = ((byte[]) o).length;
    } else if (o instanceof String) {
      contentSize = encodeUtf8((String) o, null, 0);
    } else {
      contentSize = ((ProtoBuf) o).getDataSize();
    }
    
    return tagSize + getVarIntSize(contentSize) + contentSize;
  }

  /**
   * Returns the number of bytes needed to encode the given value using 
   * WIRETYPE_VARINT
   */
  private static int getVarIntSize(long i) {
    if (i < 0) {
      return 10;
    }
    int size = 1;
    while (i >= 128) {
      size++;
      i >>= 7;
    }
    return size;
  }

  /** 
   * Writes this and nested protocol buffers to the given output stream.
   * 
   * @param os target output stream
   * @throws   IOException thrown if there is an IOException
   */
  public void outputTo(OutputStream os) throws IOException {
    for (int tag = 0; tag <= maxTag(); tag++) {
      int size = getCount(tag);
      int wireType = getWireType(tag);
      
      // ignore default values
      for (int i = 0; i < size; i++) {
        writeVarInt(os, (tag << 3) | wireType);

        switch (wireType) {
          case WIRETYPE_FIXED32:
          case WIRETYPE_FIXED64:
            long v = ((Long) getObject(tag, i, ProtoBufType.TYPE_INT64))
                .longValue();
            int cnt = (wireType == WIRETYPE_FIXED32) ? 4 : 8;
            for (int b = 0; b < cnt; b++) {
              os.write((int) (v & 0x0ff));
              v >>= 8;
            }
            break;

          case WIRETYPE_VARINT:
            v = ((Long) getObject(tag, i, ProtoBufType.TYPE_INT64)).longValue();
            if (isZigZagEncodedType(tag)) {
              v = zigZagEncode(v);
            }
            writeVarInt(os, v);
            break;

          case WIRETYPE_LENGTH_DELIMITED:
            Object o = getObject(tag, i, 
                getType(tag) == ProtoBufType.TYPE_MESSAGE 
                ? ProtoBufType.TYPE_UNDEFINED
                : ProtoBufType.TYPE_DATA);
            
            if (o instanceof byte[]){
              byte[] data = (byte[]) o;
              writeVarInt(os, data.length);
              os.write(data);
            } else {
              ProtoBuf msg = (ProtoBuf) o;
              writeVarInt(os, msg.getDataSize());
              msg.outputTo(os);
            }
            break;

          case WIRETYPE_START_GROUP:
            ((ProtoBuf) getObject(tag, i, ProtoBufType.TYPE_GROUP))
                .outputTo(os);
            writeVarInt(os, (tag << 3) | WIRETYPE_END_GROUP);
            break;
            
          default:
            throw new IllegalArgumentException();
        }
      }
    }
  }

  /**
   * Returns true if the given tag has a signed type that should be ZigZag-
   * encoded on the wire.
   *
   * ZigZag encoding turns a signed number into
   * a non-negative number by mapping negative input numbers to positive odd
   * numbers in the output space, and positive input numbers to positive even
   * numbers in the output space.  This is useful because the wire format
   * for protocol buffers requires a large number of bytes to encode
   * negative integers, while positive integers take up a smaller number
   * of bytes proportional to their magnitude.
   */
  private boolean isZigZagEncodedType(int tag) {
    int declaredType = getType(tag);
    return declaredType == ProtoBufType.TYPE_SINT32 ||
        declaredType == ProtoBufType.TYPE_SINT64;
  }

  /**
   * Converts a signed number into a non-negative ZigZag-encoded number.
   */
  private static long zigZagEncode(long v) {
    v = ((v << 1) ^ -(v >>> 63));
    return v;
  }

  /**
   * Converts a non-negative ZigZag-encoded number back into a signed number.
   */
  private static long zigZagDecode(long v) {
    v = (v >>> 1) ^ -(v & 1);
    return v;
  }

  /**
   * Writes this and nested protocol buffers to a byte array.
   *
   * @throws IOException thrown if there is problem writing the byte array
   */
  public byte[] toByteArray() throws IOException {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    outputTo(baos);
    return baos.toByteArray();
  }
  
  /**
   * Returns the largest tag id used in this message (to simplify testing). 
   */
  public int maxTag() {
    return values.size() - 1;
  }

  /** 
   * Sets the given tag to the given boolean value. 
   */
  public void setBool(int tag, boolean value) {
    setObject(tag, value ? TRUE : FALSE);
  }

  /** 
   * Sets the given tag to the given data bytes. 
   */
  public void setBytes(int tag, byte[] value) {
    setObject(tag, value);
  }

  /** 
   * Sets the given tag to the given integer value. 
   */
  public void setInt(int tag, int value) {
    setLong(tag, value);
  }

  /** 
   * Sets the given tag to the given long value.
   */
  public void setLong(int tag, long value) {
    setObject(tag, value >= 0 && value < SMALL_NUMBERS.length
        ? SMALL_NUMBERS[(int) value] : new Long(value));
  }

  /**
   * Sets the given tag to the given double value.
   */
  public void setDouble(int tag, double value) {
    setLong(tag, Double.doubleToLongBits(value));
  }

  /**
   * Sets the given tag to the given float value.
   */
  public void setFloat(int tag, float value) {
    setInt(tag, Float.floatToIntBits(value));
  }

  /** 
   * Sets the given tag to the given Group or nested Message. 
   */
  public void setProtoBuf(int tag, ProtoBuf pb) {
    setObject(tag, pb);
  }

  /**
   * Sets a new protobuf for the specified tag, setting the child protobuf's
   * type correctly for the tag.
   * @param tag the tag for which to create a new protobuf
   * @return the newly created protobuf
   */
  public ProtoBuf setNewProtoBuf(int tag) {
    ProtoBuf child = newProtoBufForTag(tag);
    setProtoBuf(tag, child);
    return child;
  }

  /** 
   * Sets the given tag to the given String value. 
   */
  public void setString(int tag, String value) {
    setObject(tag, value);
  }

  /** 
   * Inserts the given boolean value for the given tag at the given index. 
   */
  public void insertBool(int tag, int index, boolean value) {
    insertObject(tag, index, value ? TRUE : FALSE);
  }

  /** 
   * Inserts the given byte array value for the given tag at the given index. 
   */
  public void insertBytes(int tag, int index, byte[] value) {
    insertObject(tag, index, value);
  }

  /** 
   * Inserts the given int value for the given tag at the given index. 
   */
  public void insertInt(int tag, int index, int value) {
    insertLong(tag, index, value);
  }

  /** 
   * Inserts the given long value for the given tag at the given index. 
   */
  public void insertLong(int tag, int index, long value) {
    insertObject(tag, index, value >= 0 && value < SMALL_NUMBERS.length
        ? SMALL_NUMBERS[(int) value] : new Long(value));
  }

  /**
   * Inserts the given float value for the given tag at the given index.
   */
  public void insertFloat(int tag, int index, float value) {
    insertInt(tag, index, Float.floatToIntBits(value));
  }

  /**
   * Inserts the given double value for the given tag at the given index.
   */
  public void insertDouble(int tag, int index, double value) {
    insertLong(tag, index, Double.doubleToLongBits(value));
  }

  /** 
   * Inserts the given group or message for the given tag at the given index. 
   */
  public void insertProtoBuf(int tag, int index, ProtoBuf pb) {
    insertObject(tag, index, pb);
  }

  /** 
   * Inserts the given string value for the given tag at the given index. 
   */
  public void insertString(int tag, int index, String value) {
    insertObject(tag, index, value);
  }

  // ----------------- private stuff below this line ------------------------

  private void assertTypeMatch(int tag, Object object){
    int tagType = getType(tag);
    if (tagType == ProtoBufType.TYPE_UNDEFINED && msgType == null) {
      return;
    }
    
    if (object instanceof Boolean) {
      if (tagType == ProtoBufType.TYPE_BOOL 
          || tagType == WIRETYPE_VARINT) {
        return;
      }
    } else if (object instanceof Long) {
      switch(tagType){
        case WIRETYPE_FIXED32:
        case WIRETYPE_FIXED64:
        case WIRETYPE_VARINT:
        case ProtoBufType.TYPE_BOOL:
        case ProtoBufType.TYPE_ENUM:
        case ProtoBufType.TYPE_FIXED32:
        case ProtoBufType.TYPE_FIXED64:
        case ProtoBufType.TYPE_INT32:
        case ProtoBufType.TYPE_INT64:
        case ProtoBufType.TYPE_SFIXED32:
        case ProtoBufType.TYPE_SFIXED64:
        case ProtoBufType.TYPE_UINT32:
        case ProtoBufType.TYPE_UINT64:
        case ProtoBufType.TYPE_SINT32:
        case ProtoBufType.TYPE_SINT64:
        case ProtoBufType.TYPE_FLOAT:
        case ProtoBufType.TYPE_DOUBLE:
          return;
      }
    } else if (object instanceof byte[]){
      switch (tagType){
        case WIRETYPE_LENGTH_DELIMITED:
        case ProtoBufType.TYPE_DATA:
        case ProtoBufType.TYPE_MESSAGE:
        case ProtoBufType.TYPE_TEXT:
        case ProtoBufType.TYPE_BYTES:
        case ProtoBufType.TYPE_STRING:
          return;
      }
    } else if (object instanceof ProtoBuf) {
      switch (tagType){
        case WIRETYPE_LENGTH_DELIMITED:
        case WIRETYPE_START_GROUP:
        case ProtoBufType.TYPE_DATA:
        case ProtoBufType.TYPE_GROUP:
        case ProtoBufType.TYPE_MESSAGE:
          if (msgType == null || msgType.getData(tag) == null ||
              ((ProtoBuf) object).msgType == null || 
              ((ProtoBuf) object).msgType == msgType.getData(tag)) {
            return;
          }
      }
    } else if (object instanceof String){
      switch (tagType){
        case WIRETYPE_LENGTH_DELIMITED:
        case ProtoBufType.TYPE_DATA:
        case ProtoBufType.TYPE_TEXT:
        case ProtoBufType.TYPE_STRING:
          return;
      }
    }
    throw new IllegalArgumentException(MSG_MISMATCH + " type:" + msgType + 
        " tag:" + tag);
  }

  /**
   * Returns the default value for the given tag.
   */
  private Object getDefault(int tag){

    switch(getType(tag)){
      case ProtoBufType.TYPE_UNDEFINED:
      case ProtoBufType.TYPE_GROUP:
      case ProtoBufType.TYPE_MESSAGE:
        return null;
      default:
        return msgType.getData(tag);
    }
  }
  
  /** 
   * Returns the indicated value converted to the given type. 
   * 
   * @throws ArrayIndexOutOfBoundsException for invalid tags and indices
   * @throws IllegalArgumentException if count is greater than one.
   */
  private Object getObject(int tag, int desiredType) {

    int count = getCount(tag);
    
    if (count == 0){
      return getDefault(tag);
    }
    
    if (count > 1){
      throw new IllegalArgumentException();
    }

    return getObject(tag, 0, desiredType);
  }

  /** 
   * Returns the indicated value converted to the given type. 
   * 
   * @throws ArrayIndexOutOfBoundsException for invalid tags and indices
   */
  private Object getObject(int tag, int index, int desiredType) {

    if (index >= getCount(tag)) {
      throw new ArrayIndexOutOfBoundsException();
    }

    Object o = values.elementAt(tag);
    
    Vector v = null;
    if (o instanceof Vector) {
      v = (Vector) o;
      o = v.elementAt(index);
    } 
    
    Object o2 = convert(o, desiredType);

    if (o2 != o && o != null) {
      if (v == null){
        setObject(tag, o2);
      } else {
        v.setElementAt(o2, index);
      }
    }
    
    return o2;
  }

  /** 
   * Returns the wire type for the given tag. Calls getType() internally,
   * so a wire type should be found for all non-empty tags, even if no
   * message type is set and the tag was not previously read.
   */
  private final int getWireType(int tag) {

    int tagType = getType(tag);
    
    switch (tagType) {
      case WIRETYPE_VARINT:
      case WIRETYPE_FIXED32:
      case WIRETYPE_FIXED64:
      case WIRETYPE_LENGTH_DELIMITED:
      case WIRETYPE_START_GROUP:
      case ProtoBufType.TYPE_UNDEFINED:
        return tagType;
      
      case ProtoBufType.TYPE_BOOL:
      case ProtoBufType.TYPE_INT32:
      case ProtoBufType.TYPE_INT64:
      case ProtoBufType.TYPE_UINT32:
      case ProtoBufType.TYPE_UINT64:
      case ProtoBufType.TYPE_SINT32:
      case ProtoBufType.TYPE_SINT64:
      case ProtoBufType.TYPE_ENUM:
        return WIRETYPE_VARINT;
      case ProtoBufType.TYPE_DATA:
      case ProtoBufType.TYPE_MESSAGE:
      case ProtoBufType.TYPE_TEXT:
      case ProtoBufType.TYPE_BYTES:
      case ProtoBufType.TYPE_STRING:
        return WIRETYPE_LENGTH_DELIMITED;
      case ProtoBufType.TYPE_DOUBLE:
      case ProtoBufType.TYPE_FIXED64:
      case ProtoBufType.TYPE_SFIXED64:
        return WIRETYPE_FIXED64;
      case ProtoBufType.TYPE_FLOAT:
      case ProtoBufType.TYPE_FIXED32:
      case ProtoBufType.TYPE_SFIXED32:
        return WIRETYPE_FIXED32;
      case ProtoBufType.TYPE_GROUP:
        return WIRETYPE_START_GROUP;
      default:
        throw new RuntimeException(MSG_UNSUPPORTED + ':' + msgType + '/' + 
            tag + '/' + tagType);
    }
  }
  
  /** 
   * Inserts a value.
   */
  private void insertObject(int tag, int index, Object o) {
    assertTypeMatch(tag, o);
    
    int count = getCount(tag);

    if (count == 0) {
      setObject(tag, o);
    } else {
      Object curr = values.elementAt(tag);
      Vector v;
      if (curr instanceof Vector) {
        v = (Vector) curr;
      } else {
        v = new Vector();
        v.addElement(curr);
        values.setElementAt(v, tag);
      }
      v.insertElementAt(o, index);
    }
  }

  /**
   * Converts the object if a better suited class exists for the given .proto 
   * type. If the formats are not compatible, an exception is thrown.
   */
  private Object convert(Object obj, int tagType) {
    switch (tagType) {
      case ProtoBufType.TYPE_UNDEFINED:
        return obj;

      case ProtoBufType.TYPE_BOOL:
        if (obj instanceof Boolean) {
          return obj;
        }
        switch ((int) ((Long) obj).longValue()) {
          case 0:
            return FALSE;
          case 1:
            return TRUE;
          default:
            throw new IllegalArgumentException(MSG_MISMATCH);
        }
      case ProtoBufType.TYPE_FIXED32:
      case ProtoBufType.TYPE_FIXED64:
      case ProtoBufType.TYPE_INT32:
      case ProtoBufType.TYPE_INT64:
      case ProtoBufType.TYPE_SFIXED32:
      case ProtoBufType.TYPE_SFIXED64:
      case ProtoBufType.TYPE_SINT32:
      case ProtoBufType.TYPE_SINT64:
        if (obj instanceof Boolean) {
          return SMALL_NUMBERS[((Boolean) obj).booleanValue() ? 1 : 0];
        }
        return obj;
      case ProtoBufType.TYPE_DATA:
      case ProtoBufType.TYPE_BYTES:
        if (obj instanceof String) {
          return encodeUtf8((String) obj);
        } else if (obj instanceof ProtoBuf) {
          ByteArrayOutputStream buf = new ByteArrayOutputStream();
          try {
            ((ProtoBuf) obj).outputTo(buf);
            return buf.toByteArray();
          } catch (IOException e) {
            throw new RuntimeException(e.toString());
          }
        }
        return obj;
      case ProtoBufType.TYPE_TEXT:
      case ProtoBufType.TYPE_STRING:
        if (obj instanceof byte[]) {
          byte[] data = (byte[]) obj;
          return decodeUtf8(data, 0, data.length, true);
        }
        return obj;
      case ProtoBufType.TYPE_GROUP:
      case ProtoBufType.TYPE_MESSAGE:
        if (obj instanceof byte[]) {
          try {
            return new ProtoBuf(null).parse((byte[]) obj);
          } catch (IOException e) {
            throw new RuntimeException(e.toString());
          }
        }
        return obj;
      default:
        // default includes FLOAT and DOUBLE
        throw new RuntimeException(MSG_UNSUPPORTED);
    }
  }

  /** 
   * Reads a variable-size integer (up to 10 bytes for 64 bit) from the 
   * given input stream.
   * 
   * @param is        the stream to read from
   * @param permitEOF if true, -1 is returned when EOF is reached instead of
   *                  throwing an IOException
   * @return          the integer value read from the stream, or -1 if EOF is
   *                  reached and permitEOF is true
   * @throws          IOException thrown for underlying IO issues and if EOF
   *                  is reached and permitEOF is false
   */
  static long readVarInt(InputStream is, boolean permitEOF) throws IOException {

    long result = 0;
    int shift = 0;

    // max 10 byte wire format for 64 bit integer (7 bit data per byte)

    for (int i = 0; i < VARINT_MAX_BYTES; i++) {
      int in = is.read();

      if (in == -1) {
        if (i == 0 && permitEOF) {
          return -1;
        } else {
          throw new IOException("EOF");
        }
      }
      result |= ((long) (in & 0x07f)) << shift;

      if ((in & 0x80) == 0){
        break; // get out early
      }
      
      shift += 7;
    }
    return result;
  }

  /**
   * Internal helper method to set a (single) value. Overwrites all existing 
   * values.
   */
  private void setObject(int tag, Object o) {
    if (values.size() <= tag) {
      values.setSize(tag + 1);
    }
    if (o != null) {
      assertTypeMatch(tag, o);
    }
    values.setElementAt(o, tag);
  }

  /** 
   * Write a variable-size integer to the given output stream.
   */
  static void writeVarInt(OutputStream os, long value) throws IOException {
    for (int i = 0; i < VARINT_MAX_BYTES; i++) {

      int toWrite = (int) (value & 0x7f);

      value >>>= 7;

      if (value == 0) {
        os.write(toWrite);
        break;
      } else {
        os.write(toWrite | 0x080);
      }
    }
  }

    /**
   * Returns a byte array containing the given string, encoded as UTF-8. The
   * returned byte array contains at least s.length() bytes and at most
   * 4 * s.length() bytes. UTF-16 surrogates are transcoded to UTF-8.
   *
   * @param s input string to be encoded
   * @return UTF-8 encoded input string
   */
  static byte[] encodeUtf8(String s) {
    int len = encodeUtf8(s, null, 0);
    byte[] result = new byte[len];
    encodeUtf8(s, result, 0);
    return result;
  }

  /**
   * Encodes the given string to UTF-8 in the given buffer or calculates
   * the space needed if the buffer is null.
   *
   * @param s the string to be UTF-8 encoded
   * @param buf byte array to write to
   * @return new buffer position after writing (which equals the required size
   *    if pos is 0)
   */
  static int encodeUtf8(String s, byte[] buf, int pos){
    int len = s.length();
    for (int i = 0; i < len; i++){
      int code = s.charAt(i);

      // surrogate 0xd800 .. 0xdfff?
      if (code >= 0x0d800 && code <= 0x0dfff && i + 1 < len){
        int codeLo = s.charAt(i + 1);

        // 0xfc00 is the surrogate id mask (first six bit of 16 set)
        // 0x03ff is the surrogate data mask (remaining 10 bit)
        // check if actually a surrogate pair (d800 ^ dc00 == 0400)
        if (((codeLo & 0xfc00) ^ (code & 0x0fc00)) == 0x0400){

          i += 1;

          int codeHi;
          if ((codeLo & 0xfc00) == 0x0d800){
            codeHi = codeLo;
            codeLo = code;
          } else {
            codeHi = code;
          }
          code = (((codeHi & 0x3ff) << 10) | (codeLo & 0x3ff)) + 0x10000;
        }
      }
      if (code <= 0x007f) {
        if (buf != null){
          buf[pos] = (byte) code;
        }
        pos += 1;
      } else if (code <= 0x07FF) {
        // non-ASCII <= 0x7FF
        if (buf != null){
          buf[pos] = (byte) (0xc0 | (code >> 6));
          buf[pos + 1] = (byte) (0x80 | (code & 0x3F));
        }
        pos += 2;
      } else if (code <= 0xFFFF){
        // 0x7FF < code <= 0xFFFF
        if (buf != null){
          buf[pos] = (byte) ((0xe0 | (code >> 12)));
          buf[pos + 1] = (byte) ((0x80 | ((code >> 6) & 0x3F)));
          buf[pos + 2] = (byte) ((0x80 | (code & 0x3F)));
        }
        pos += 3;
      } else {
        if (buf != null){
          buf[pos] = (byte) ((0xf0 | (code >> 18)));
          buf[pos + 1] = (byte) ((0x80 | ((code >> 12) & 0x3F)));
          buf[pos + 2] = (byte) ((0x80 | ((code >> 6) & 0x3F)));
          buf[pos + 3] = (byte) ((0x80 | (code & 0x3F)));
        }
        pos += 4;
      }
    }

    return pos;
  }

  /**
   * Decodes an array of UTF-8 bytes to a Java string (UTF-16). The tolerant
   * flag determines what to do in case of illegal or unsupported sequences.
   *
   * @param data input byte array containing UTF-8 data
   * @param start decoding start position in byte array
   * @param end decoding end position in byte array
   * @param tolerant if true, an IllegalArgumentException is thrown for illegal
   *    UTF-8 codes
   * @return the string containing the UTF-8 decoding result
   */
  static String decodeUtf8(byte[] data, int start, int end,
      boolean tolerant){

    StringBuffer sb = new StringBuffer(end - start);
    int pos = start;

    while (pos < end){
      int b = data[pos++] & 0x0ff;
      if (b <= 0x7f){
        sb.append((char) b);
      } else if (b >= 0xf5){ // byte sequence too long
        if (!tolerant){
          throw new IllegalArgumentException("Invalid UTF8");
        }
        sb.append((char) b);
      } else {
        int border = 0xe0;
        int count = 1;
        int minCode = 128;
        int mask = 0x01f;
        while (b >= border){
          border = (border >> 1) | 0x80;
          minCode = minCode << (count == 1 ? 4 : 5);
          count++;
          mask = mask >> 1;
        }
        int code = b & mask;

        for (int i = 0; i < count; i++){
          code = code << 6;
          if (pos >= end){
            if (!tolerant){
              throw new IllegalArgumentException("Invalid UTF8");
            }
            // otherwise, assume zeroes
          } else {
            if (!tolerant && (data[pos] & 0xc0) != 0x80){
              throw new IllegalArgumentException("Invalid UTF8");
            }
            code |= (data[pos++] & 0x3f); // six bit
          }
        }

        // illegal code or surrogate code
        if (!tolerant && code < minCode || (code >= 0xd800 && code <= 0xdfff)){
          throw new IllegalArgumentException("Invalid UTF8");
        }

        if (code <= 0x0ffff){
          sb.append((char) code);
        } else { // surrogate UTF16
          code -= 0x10000;
          sb.append((char) (0xd800 | (code >> 10))); // high 10 bit
          sb.append((char) (0xdc00 | (code & 0x3ff))); // low 10 bit
        }
      }
    }
    return sb.toString();
  }

}