1 /**********
2 This library is free software; you can redistribute it and/or modify it under
3 the terms of the GNU Lesser General Public License as published by the
4 Free Software Foundation; either version 3 of the License, or (at your
5 option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6
7 This library is distributed in the hope that it will be useful, but WITHOUT
8 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10 more details.
11
12 You should have received a copy of the GNU Lesser General Public License
13 along with this library; if not, write to the Free Software Foundation, Inc.,
14 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15 **********/
16 // "liveMedia"
17 // Copyright (c) 1996-2020 Live Networks, Inc. All rights reserved.
18 // A class that encapsulates a Matroska file.
19 // Implementation
20
21 #include "MatroskaFileParser.hh"
22 #include "MatroskaDemuxedTrack.hh"
23 #include <ByteStreamFileSource.hh>
24 #include <H264VideoStreamDiscreteFramer.hh>
25 #include <H265VideoStreamDiscreteFramer.hh>
26 #include <MPEG1or2AudioRTPSink.hh>
27 #include <MPEG4GenericRTPSink.hh>
28 #include <AC3AudioRTPSink.hh>
29 #include <SimpleRTPSink.hh>
30 #include <VorbisAudioRTPSink.hh>
31 #include <H264VideoRTPSink.hh>
32 #include <H265VideoRTPSink.hh>
33 #include <VP8VideoRTPSink.hh>
34 #include <VP9VideoRTPSink.hh>
35 #include <TheoraVideoRTPSink.hh>
36 #include <RawVideoRTPSink.hh>
37 #include <T140TextRTPSink.hh>
38 #include <Base64.hh>
39 #include <H264VideoFileSink.hh>
40 #include <H265VideoFileSink.hh>
41 #include <AMRAudioFileSink.hh>
42 #include <OggFileSink.hh>
43
44 ////////// CuePoint definition //////////
45
46 class CuePoint {
47 public:
48 CuePoint(double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster/* 1-based */);
49 virtual ~CuePoint();
50
51 static void addCuePoint(CuePoint*& root, double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster/* 1-based */,
52 Boolean& needToReviseBalanceOfParent);
53 // If "cueTime" == "root.fCueTime", replace the existing data, otherwise add to the left or right subtree.
54 // (Note that this is a static member function because - as a result of tree rotation - "root" might change.)
55
56 Boolean lookup(double& cueTime, u_int64_t& resultClusterOffsetInFile, unsigned& resultBlockNumWithinCluster);
57
58 static void fprintf(FILE* fid, CuePoint* cuePoint); // used for debugging; it's static to allow for "cuePoint == NULL"
59
60 private:
61 // The "CuePoint" tree is implemented as an AVL Tree, to keep it balanced (for efficient lookup).
62 CuePoint* fSubTree[2]; // 0 => left; 1 => right
left() const63 CuePoint* left() const { return fSubTree[0]; }
right() const64 CuePoint* right() const { return fSubTree[1]; }
65 char fBalance; // height of right subtree - height of left subtree
66
67 static void rotate(unsigned direction/*0 => left; 1 => right*/, CuePoint*& root); // used to keep the tree in balance
68
69 double fCueTime;
70 u_int64_t fClusterOffsetInFile;
71 unsigned fBlockNumWithinCluster; // 0-based
72 };
73
74 UsageEnvironment& operator<<(UsageEnvironment& env, const CuePoint* cuePoint); // used for debugging
75
76
77 ////////// MatroskaTrackTable definition /////////
78
79 // For looking up and iterating over the file's tracks:
80 class MatroskaTrackTable {
81 public:
82 MatroskaTrackTable();
83 virtual ~MatroskaTrackTable();
84
85 void add(MatroskaTrack* newTrack, unsigned trackNumber);
86 MatroskaTrack* lookup(unsigned trackNumber);
87
88 unsigned numTracks() const;
89
90 class Iterator {
91 public:
92 Iterator(MatroskaTrackTable& ourTable);
93 virtual ~Iterator();
94 MatroskaTrack* next();
95 private:
96 HashTable::Iterator* fIter;
97 };
98
99 private:
100 friend class Iterator;
101 HashTable* fTable;
102 };
103
104
105
106 ////////// MatroskaFile implementation //////////
107
108 void MatroskaFile
createNew(UsageEnvironment & env,char const * fileName,onCreationFunc * onCreation,void * onCreationClientData,char const * preferredLanguage)109 ::createNew(UsageEnvironment& env, char const* fileName, onCreationFunc* onCreation, void* onCreationClientData,
110 char const* preferredLanguage) {
111 new MatroskaFile(env, fileName, onCreation, onCreationClientData, preferredLanguage);
112 }
113
MatroskaFile(UsageEnvironment & env,char const * fileName,onCreationFunc * onCreation,void * onCreationClientData,char const * preferredLanguage)114 MatroskaFile::MatroskaFile(UsageEnvironment& env, char const* fileName, onCreationFunc* onCreation, void* onCreationClientData,
115 char const* preferredLanguage)
116 : Medium(env),
117 fFileName(strDup(fileName)), fOnCreation(onCreation), fOnCreationClientData(onCreationClientData),
118 fPreferredLanguage(strDup(preferredLanguage)),
119 fTimecodeScale(1000000), fSegmentDuration(0.0), fSegmentDataOffset(0), fClusterOffset(0), fCuesOffset(0), fCuePoints(NULL),
120 fChosenVideoTrackNumber(0), fChosenAudioTrackNumber(0), fChosenSubtitleTrackNumber(0) {
121 fTrackTable = new MatroskaTrackTable;
122 fDemuxesTable = HashTable::create(ONE_WORD_HASH_KEYS);
123
124 FramedSource* inputSource = ByteStreamFileSource::createNew(envir(), fileName);
125 if (inputSource == NULL) {
126 // The specified input file does not exist!
127 fParserForInitialization = NULL;
128 handleEndOfTrackHeaderParsing(); // we have no file, and thus no tracks, but we still need to signal this
129 } else {
130 // Initialize ourselves by parsing the file's 'Track' headers:
131 fParserForInitialization = new MatroskaFileParser(*this, inputSource, handleEndOfTrackHeaderParsing, this, NULL);
132 }
133 }
134
~MatroskaFile()135 MatroskaFile::~MatroskaFile() {
136 delete fParserForInitialization;
137 delete fCuePoints;
138
139 // Delete any outstanding "MatroskaDemux"s, and the table for them:
140 MatroskaDemux* demux;
141 while ((demux = (MatroskaDemux*)fDemuxesTable->RemoveNext()) != NULL) {
142 delete demux;
143 }
144 delete fDemuxesTable;
145 delete fTrackTable;
146
147 delete[] (char*)fPreferredLanguage;
148 delete[] (char*)fFileName;
149 }
150
handleEndOfTrackHeaderParsing(void * clientData)151 void MatroskaFile::handleEndOfTrackHeaderParsing(void* clientData) {
152 ((MatroskaFile*)clientData)->handleEndOfTrackHeaderParsing();
153 }
154
155 class TrackChoiceRecord {
156 public:
157 unsigned trackNumber;
158 u_int8_t trackType;
159 unsigned choiceFlags;
160 };
161
handleEndOfTrackHeaderParsing()162 void MatroskaFile::handleEndOfTrackHeaderParsing() {
163 // Having parsed all of our track headers, iterate through the tracks to figure out which ones should be played.
164 // The Matroska 'specification' is rather imprecise about this (as usual). However, we use the following algorithm:
165 // - Use one (but no more) enabled track of each type (video, audio, subtitle). (Ignore all tracks that are not 'enabled'.)
166 // - For each track type, choose the one that's 'forced'.
167 // - If more than one is 'forced', choose the first one that matches our preferred language, or the first if none matches.
168 // - If none is 'forced', choose the one that's 'default'.
169 // - If more than one is 'default', choose the first one that matches our preferred language, or the first if none matches.
170 // - If none is 'default', choose the first one that matches our preferred language, or the first if none matches.
171 unsigned numTracks = fTrackTable->numTracks();
172 if (numTracks > 0) {
173 TrackChoiceRecord* trackChoice = new TrackChoiceRecord[numTracks];
174 unsigned numEnabledTracks = 0;
175 MatroskaTrackTable::Iterator iter(*fTrackTable);
176 MatroskaTrack* track;
177 while ((track = iter.next()) != NULL) {
178 if (!track->isEnabled || track->trackType == 0 || track->mimeType[0] == '\0') continue; // track not enabled, or not fully-defined
179
180 trackChoice[numEnabledTracks].trackNumber = track->trackNumber;
181 trackChoice[numEnabledTracks].trackType = track->trackType;
182
183 // Assign flags for this track so that, when sorted, the largest value becomes our choice:
184 unsigned choiceFlags = 0;
185 if (fPreferredLanguage != NULL && track->language != NULL && strcmp(fPreferredLanguage, track->language) == 0) {
186 // This track matches our preferred language:
187 choiceFlags |= 1;
188 }
189 if (track->isForced) {
190 choiceFlags |= 4;
191 } else if (track->isDefault) {
192 choiceFlags |= 2;
193 }
194 trackChoice[numEnabledTracks].choiceFlags = choiceFlags;
195
196 ++numEnabledTracks;
197 }
198
199 // Choose the desired track for each track type:
200 for (u_int8_t trackType = 0x01; trackType != MATROSKA_TRACK_TYPE_OTHER; trackType <<= 1) {
201 int bestNum = -1;
202 int bestChoiceFlags = -1;
203 for (unsigned i = 0; i < numEnabledTracks; ++i) {
204 if (trackChoice[i].trackType == trackType && (int)trackChoice[i].choiceFlags > bestChoiceFlags) {
205 bestNum = i;
206 bestChoiceFlags = (int)trackChoice[i].choiceFlags;
207 }
208 }
209 if (bestChoiceFlags >= 0) { // There is a track for this track type
210 if (trackType == MATROSKA_TRACK_TYPE_VIDEO) fChosenVideoTrackNumber = trackChoice[bestNum].trackNumber;
211 else if (trackType == MATROSKA_TRACK_TYPE_AUDIO) fChosenAudioTrackNumber = trackChoice[bestNum].trackNumber;
212 else fChosenSubtitleTrackNumber = trackChoice[bestNum].trackNumber;
213 }
214 }
215
216 delete[] trackChoice;
217 }
218
219 #ifdef DEBUG
220 if (fChosenVideoTrackNumber > 0) fprintf(stderr, "Chosen video track: #%d\n", fChosenVideoTrackNumber); else fprintf(stderr, "No chosen video track\n");
221 if (fChosenAudioTrackNumber > 0) fprintf(stderr, "Chosen audio track: #%d\n", fChosenAudioTrackNumber); else fprintf(stderr, "No chosen audio track\n");
222 if (fChosenSubtitleTrackNumber > 0) fprintf(stderr, "Chosen subtitle track: #%d\n", fChosenSubtitleTrackNumber); else fprintf(stderr, "No chosen subtitle track\n");
223 #endif
224
225 // Delete our parser, because it's done its job now:
226 delete fParserForInitialization; fParserForInitialization = NULL;
227
228 // Finally, signal our caller that we've been created and initialized:
229 if (fOnCreation != NULL) (*fOnCreation)(this, fOnCreationClientData);
230 }
231
lookup(unsigned trackNumber) const232 MatroskaTrack* MatroskaFile::lookup(unsigned trackNumber) const {
233 return fTrackTable->lookup(trackNumber);
234 }
235
newDemux()236 MatroskaDemux* MatroskaFile::newDemux() {
237 MatroskaDemux* demux = new MatroskaDemux(*this);
238 fDemuxesTable->Add((char const*)demux, demux);
239
240 return demux;
241 }
242
removeDemux(MatroskaDemux * demux)243 void MatroskaFile::removeDemux(MatroskaDemux* demux) {
244 fDemuxesTable->Remove((char const*)demux);
245 }
246
247 #define getPrivByte(b) if (n == 0) break; else do {b = *p++; --n;} while (0) /* Vorbis/Theora configuration header parsing */
248 #define CHECK_PTR if (ptr >= limit) break /* H.264/H.265 parsing */
249 #define NUM_BYTES_REMAINING (unsigned)(limit - ptr) /* H.264/H.265 parsing */
250
getH264ConfigData(MatroskaTrack const * track,u_int8_t * & sps,unsigned & spsSize,u_int8_t * & pps,unsigned & ppsSize)251 void MatroskaFile::getH264ConfigData(MatroskaTrack const* track,
252 u_int8_t*& sps, unsigned& spsSize,
253 u_int8_t*& pps, unsigned& ppsSize) {
254 sps = pps = NULL;
255 spsSize = ppsSize = 0;
256
257 do {
258 if (track == NULL) break;
259
260 // Use our track's 'Codec Private' data: Bytes 5 and beyond contain SPS and PPSs:
261 if (track->codecPrivateSize < 6) break;
262 u_int8_t* SPSandPPSBytes = &track->codecPrivate[5];
263 unsigned numSPSandPPSBytes = track->codecPrivateSize - 5;
264
265 // Extract, from "SPSandPPSBytes", one SPS NAL unit, and one PPS NAL unit.
266 // (I hope one is all we need of each.)
267 unsigned i;
268 u_int8_t* ptr = SPSandPPSBytes;
269 u_int8_t* limit = &SPSandPPSBytes[numSPSandPPSBytes];
270
271 unsigned numSPSs = (*ptr++)&0x1F; CHECK_PTR;
272 for (i = 0; i < numSPSs; ++i) {
273 unsigned spsSize1 = (*ptr++)<<8; CHECK_PTR;
274 spsSize1 |= *ptr++; CHECK_PTR;
275
276 if (spsSize1 > NUM_BYTES_REMAINING) break;
277 u_int8_t nal_unit_type = ptr[0]&0x1F;
278 if (sps == NULL && nal_unit_type == 7/*sanity check*/) { // save the first one
279 spsSize = spsSize1;
280 sps = new u_int8_t[spsSize];
281 memmove(sps, ptr, spsSize);
282 }
283 ptr += spsSize1;
284 }
285
286 unsigned numPPSs = (*ptr++)&0x1F; CHECK_PTR;
287 for (i = 0; i < numPPSs; ++i) {
288 unsigned ppsSize1 = (*ptr++)<<8; CHECK_PTR;
289 ppsSize1 |= *ptr++; CHECK_PTR;
290
291 if (ppsSize1 > NUM_BYTES_REMAINING) break;
292 u_int8_t nal_unit_type = ptr[0]&0x1F;
293 if (pps == NULL && nal_unit_type == 8/*sanity check*/) { // save the first one
294 ppsSize = ppsSize1;
295 pps = new u_int8_t[ppsSize];
296 memmove(pps, ptr, ppsSize);
297 }
298 ptr += ppsSize1;
299 }
300
301 return;
302 } while (0);
303
304 // An error occurred:
305 delete[] sps; sps = NULL; spsSize = 0;
306 delete[] pps; pps = NULL; ppsSize = 0;
307 }
308
getH265ConfigData(MatroskaTrack const * track,u_int8_t * & vps,unsigned & vpsSize,u_int8_t * & sps,unsigned & spsSize,u_int8_t * & pps,unsigned & ppsSize)309 void MatroskaFile::getH265ConfigData(MatroskaTrack const* track,
310 u_int8_t*& vps, unsigned& vpsSize,
311 u_int8_t*& sps, unsigned& spsSize,
312 u_int8_t*& pps, unsigned& ppsSize) {
313 vps = sps = pps = NULL;
314 vpsSize = spsSize = ppsSize = 0;
315
316 do {
317 if (track == NULL) break;
318
319 u_int8_t* VPS_SPS_PPSBytes = NULL; unsigned numVPS_SPS_PPSBytes = 0;
320 unsigned i;
321
322 if (track->codecPrivateUsesH264FormatForH265) {
323 // The data uses the H.264-style format (but including VPS NAL unit(s)).
324 // The VPS,SPS,PPS NAL unit information starts at byte #5:
325 if (track->codecPrivateSize >= 6) {
326 numVPS_SPS_PPSBytes = track->codecPrivateSize - 5;
327 VPS_SPS_PPSBytes = &track->codecPrivate[5];
328 }
329 } else {
330 // The data uses the proper H.265-style format.
331 // The VPS,SPS,PPS NAL unit information starts at byte #22:
332 if (track->codecPrivateSize >= 23) {
333 numVPS_SPS_PPSBytes = track->codecPrivateSize - 22;
334 VPS_SPS_PPSBytes = &track->codecPrivate[22];
335 }
336 }
337 if (VPS_SPS_PPSBytes == NULL) break; // no VPS,SPS,PPS NAL unit information was present
338
339 // Extract, from "VPS_SPS_PPSBytes", one VPS NAL unit, one SPS NAL unit, and one PPS NAL unit.
340 // (I hope one is all we need of each.)
341 u_int8_t* ptr = VPS_SPS_PPSBytes;
342 u_int8_t* limit = &VPS_SPS_PPSBytes[numVPS_SPS_PPSBytes];
343
344 if (track->codecPrivateUsesH264FormatForH265) {
345 // The data uses the H.264-style format (but including VPS NAL unit(s)).
346 while (NUM_BYTES_REMAINING > 0) {
347 unsigned numNALUnits = (*ptr++)&0x1F; CHECK_PTR;
348 for (i = 0; i < numNALUnits; ++i) {
349 unsigned nalUnitLength = (*ptr++)<<8; CHECK_PTR;
350 nalUnitLength |= *ptr++; CHECK_PTR;
351
352 if (nalUnitLength > NUM_BYTES_REMAINING) break;
353 u_int8_t nal_unit_type = (ptr[0]&0x7E)>>1;
354 if (nal_unit_type == 32) { // VPS
355 vpsSize = nalUnitLength;
356 delete[] vps; vps = new u_int8_t[nalUnitLength];
357 memmove(vps, ptr, nalUnitLength);
358 } else if (nal_unit_type == 33) { // SPS
359 spsSize = nalUnitLength;
360 delete[] sps; sps = new u_int8_t[nalUnitLength];
361 memmove(sps, ptr, nalUnitLength);
362 } else if (nal_unit_type == 34) { // PPS
363 ppsSize = nalUnitLength;
364 delete[] pps; pps = new u_int8_t[nalUnitLength];
365 memmove(pps, ptr, nalUnitLength);
366 }
367 ptr += nalUnitLength;
368 }
369 }
370 } else {
371 // The data uses the proper H.265-style format.
372 unsigned numOfArrays = *ptr++; CHECK_PTR;
373 for (unsigned j = 0; j < numOfArrays; ++j) {
374 ++ptr; CHECK_PTR; // skip the 'array_completeness'|'reserved'|'NAL_unit_type' byte
375
376 unsigned numNalus = (*ptr++)<<8; CHECK_PTR;
377 numNalus |= *ptr++; CHECK_PTR;
378
379 for (i = 0; i < numNalus; ++i) {
380 unsigned nalUnitLength = (*ptr++)<<8; CHECK_PTR;
381 nalUnitLength |= *ptr++; CHECK_PTR;
382
383 if (nalUnitLength > NUM_BYTES_REMAINING) break;
384 u_int8_t nal_unit_type = (ptr[0]&0x7E)>>1;
385 if (nal_unit_type == 32) { // VPS
386 vpsSize = nalUnitLength;
387 delete[] vps; vps = new u_int8_t[nalUnitLength];
388 memmove(vps, ptr, nalUnitLength);
389 } else if (nal_unit_type == 33) { // SPS
390 spsSize = nalUnitLength;
391 delete[] sps; sps = new u_int8_t[nalUnitLength];
392 memmove(sps, ptr, nalUnitLength);
393 } else if (nal_unit_type == 34) { // PPS
394 ppsSize = nalUnitLength;
395 delete[] pps; pps = new u_int8_t[nalUnitLength];
396 memmove(pps, ptr, nalUnitLength);
397 }
398 ptr += nalUnitLength;
399 }
400 }
401 }
402
403 return;
404 } while (0);
405
406 // An error occurred:
407 delete[] vps; vps = NULL; vpsSize = 0;
408 delete[] sps; sps = NULL; spsSize = 0;
409 delete[] pps; pps = NULL; ppsSize = 0;
410 }
411
412 void MatroskaFile
getVorbisOrTheoraConfigData(MatroskaTrack const * track,u_int8_t * & identificationHeader,unsigned & identificationHeaderSize,u_int8_t * & commentHeader,unsigned & commentHeaderSize,u_int8_t * & setupHeader,unsigned & setupHeaderSize)413 ::getVorbisOrTheoraConfigData(MatroskaTrack const* track,
414 u_int8_t*& identificationHeader, unsigned& identificationHeaderSize,
415 u_int8_t*& commentHeader, unsigned& commentHeaderSize,
416 u_int8_t*& setupHeader, unsigned& setupHeaderSize) {
417 identificationHeader = commentHeader = setupHeader = NULL;
418 identificationHeaderSize = commentHeaderSize = setupHeaderSize = 0;
419
420 do {
421 if (track == NULL) break;
422
423 // The Matroska file's 'Codec Private' data is assumed to be the codec configuration
424 // information, containing the "Identification", "Comment", and "Setup" headers.
425 // Extract these headers now:
426 Boolean isTheora = strcmp(track->mimeType, "video/THEORA") == 0; // otherwise, Vorbis
427 u_int8_t* p = track->codecPrivate;
428 unsigned n = track->codecPrivateSize;
429 if (n == 0 || p == NULL) break; // we have no 'Codec Private' data
430
431 u_int8_t numHeaders;
432 getPrivByte(numHeaders);
433 unsigned headerSize[3]; // we don't handle any more than 2+1 headers
434
435 // Extract the sizes of each of these headers:
436 unsigned sizesSum = 0;
437 Boolean success = True;
438 unsigned i;
439 for (i = 0; i < numHeaders && i < 3; ++i) {
440 unsigned len = 0;
441 u_int8_t c;
442
443 do {
444 success = False;
445 getPrivByte(c);
446 success = True;
447
448 len += c;
449 } while (c == 255);
450 if (!success || len == 0) break;
451
452 headerSize[i] = len;
453 sizesSum += len;
454 }
455 if (!success) break;
456
457 // Compute the implicit size of the final header:
458 if (numHeaders < 3) {
459 int finalHeaderSize = n - sizesSum;
460 if (finalHeaderSize <= 0) break; // error in data; give up
461
462 headerSize[numHeaders] = (unsigned)finalHeaderSize;
463 ++numHeaders; // include the final header now
464 } else {
465 numHeaders = 3; // The maximum number of headers that we handle
466 }
467
468 // Then, extract and classify each header:
469 for (i = 0; i < numHeaders; ++i) {
470 success = False;
471 unsigned newHeaderSize = headerSize[i];
472 u_int8_t* newHeader = new u_int8_t[newHeaderSize];
473 if (newHeader == NULL) break;
474
475 u_int8_t* hdr = newHeader;
476 while (newHeaderSize-- > 0) {
477 success = False;
478 getPrivByte(*hdr++);
479 success = True;
480 }
481 if (!success) {
482 delete[] newHeader;
483 break;
484 }
485
486 u_int8_t headerType = newHeader[0];
487 if (headerType == 1 || (isTheora && headerType == 0x80)) { // "identification" header
488 delete[] identificationHeader; identificationHeader = newHeader;
489 identificationHeaderSize = headerSize[i];
490 } else if (headerType == 3 || (isTheora && headerType == 0x81)) { // "comment" header
491 delete[] commentHeader; commentHeader = newHeader;
492 commentHeaderSize = headerSize[i];
493 } else if (headerType == 5 || (isTheora && headerType == 0x82)) { // "setup" header
494 delete[] setupHeader; setupHeader = newHeader;
495 setupHeaderSize = headerSize[i];
496 } else {
497 delete[] newHeader; // because it was a header type that we don't understand
498 }
499 }
500 if (!success) break;
501
502 return;
503 } while (0);
504
505 // An error occurred:
506 delete[] identificationHeader; identificationHeader = NULL; identificationHeaderSize = 0;
507 delete[] commentHeader; commentHeader = NULL; commentHeaderSize = 0;
508 delete[] setupHeader; setupHeader = NULL; setupHeaderSize = 0;
509 }
510
fileDuration()511 float MatroskaFile::fileDuration() {
512 if (fCuePoints == NULL) return 0.0; // Hack, because the RTSP server code assumes that duration > 0 => seekable. (fix this) #####
513
514 return segmentDuration()*(timecodeScale()/1000000000.0f);
515 }
516
517 // The size of the largest key frame that we expect. This determines our buffer sizes:
518 #define MAX_KEY_FRAME_SIZE 300000
519
520 FramedSource* MatroskaFile
createSourceForStreaming(FramedSource * baseSource,unsigned trackNumber,unsigned & estBitrate,unsigned & numFiltersInFrontOfTrack)521 ::createSourceForStreaming(FramedSource* baseSource, unsigned trackNumber,
522 unsigned& estBitrate, unsigned& numFiltersInFrontOfTrack) {
523 if (baseSource == NULL) return NULL;
524
525 FramedSource* result = baseSource; // by default
526 estBitrate = 100; // by default
527 numFiltersInFrontOfTrack = 0; // by default
528
529 // Look at the track's MIME type to set its estimated bitrate (for use by RTCP).
530 // (Later, try to be smarter about figuring out the bitrate.) #####
531 // Some MIME types also require adding a special 'framer' in front of the source.
532 MatroskaTrack* track = lookup(trackNumber);
533 if (track != NULL) { // should always be true
534 if (strcmp(track->mimeType, "audio/MPEG") == 0) {
535 estBitrate = 128;
536 } else if (strcmp(track->mimeType, "audio/AAC") == 0) {
537 estBitrate = 96;
538 } else if (strcmp(track->mimeType, "audio/AC3") == 0) {
539 estBitrate = 48;
540 } else if (strcmp(track->mimeType, "audio/VORBIS") == 0) {
541 estBitrate = 96;
542 } else if (strcmp(track->mimeType, "video/H264") == 0) {
543 estBitrate = 500;
544 // Allow for the possibility of very large NAL units being fed to the sink object:
545 OutPacketBuffer::increaseMaxSizeTo(MAX_KEY_FRAME_SIZE); // bytes
546
547 // Add a framer in front of the source:
548 result = H264VideoStreamDiscreteFramer::createNew(envir(), result);
549 ++numFiltersInFrontOfTrack;
550 } else if (strcmp(track->mimeType, "video/H265") == 0) {
551 estBitrate = 500;
552 // Allow for the possibility of very large NAL units being fed to the sink object:
553 OutPacketBuffer::increaseMaxSizeTo(MAX_KEY_FRAME_SIZE); // bytes
554
555 // Add a framer in front of the source:
556 result = H265VideoStreamDiscreteFramer::createNew(envir(), result);
557 ++numFiltersInFrontOfTrack;
558 } else if (strcmp(track->mimeType, "video/VP8") == 0) {
559 estBitrate = 500;
560 } else if (strcmp(track->mimeType, "video/VP9") == 0) {
561 estBitrate = 500;
562 } else if (strcmp(track->mimeType, "video/THEORA") == 0) {
563 estBitrate = 500;
564 } else if (strcmp(track->mimeType, "text/T140") == 0) {
565 estBitrate = 48;
566 }
567 }
568
569 return result;
570 }
571
trackMIMEType(unsigned trackNumber) const572 char const* MatroskaFile::trackMIMEType(unsigned trackNumber) const {
573 MatroskaTrack* track = lookup(trackNumber);
574 if (track == NULL) return NULL;
575
576 return track->mimeType;
577 }
578
579 RTPSink* MatroskaFile
createRTPSinkForTrackNumber(unsigned trackNumber,Groupsock * rtpGroupsock,unsigned char rtpPayloadTypeIfDynamic)580 ::createRTPSinkForTrackNumber(unsigned trackNumber, Groupsock* rtpGroupsock,
581 unsigned char rtpPayloadTypeIfDynamic) {
582 RTPSink* result = NULL; // default value, if an error occurs
583
584 do {
585 MatroskaTrack* track = lookup(trackNumber);
586 if (track == NULL) break;
587
588 if (strcmp(track->mimeType, "audio/L16") == 0) {
589 result = SimpleRTPSink::createNew(envir(), rtpGroupsock,rtpPayloadTypeIfDynamic, track->samplingFrequency, "audio", "L16", track->numChannels);
590 } else if (strcmp(track->mimeType, "audio/MPEG") == 0) {
591 result = MPEG1or2AudioRTPSink::createNew(envir(), rtpGroupsock);
592 } else if (strcmp(track->mimeType, "audio/AAC") == 0) {
593 // The Matroska file's 'Codec Private' data is assumed to be the AAC configuration
594 // information. Use this to generate a hexadecimal 'config' string for the new RTP sink:
595 char* configStr = new char[2*track->codecPrivateSize + 1]; if (configStr == NULL) break;
596 // 2 hex digits per byte, plus the trailing '\0'
597 for (unsigned i = 0; i < track->codecPrivateSize; ++i) {
598 sprintf(&configStr[2*i], "%02X", track->codecPrivate[i]);
599 }
600
601 result = MPEG4GenericRTPSink::createNew(envir(), rtpGroupsock,
602 rtpPayloadTypeIfDynamic,
603 track->samplingFrequency,
604 "audio", "AAC-hbr", configStr,
605 track->numChannels);
606 delete[] configStr;
607 } else if (strcmp(track->mimeType, "audio/AC3") == 0) {
608 result = AC3AudioRTPSink
609 ::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic, track->samplingFrequency);
610 } else if (strcmp(track->mimeType, "audio/OPUS") == 0) {
611 result = SimpleRTPSink
612 ::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic,
613 48000, "audio", "OPUS", 2, False/*only 1 Opus 'packet' in each RTP packet*/);
614 } else if (strcmp(track->mimeType, "audio/VORBIS") == 0 || strcmp(track->mimeType, "video/THEORA") == 0) {
615 u_int8_t* identificationHeader; unsigned identificationHeaderSize;
616 u_int8_t* commentHeader; unsigned commentHeaderSize;
617 u_int8_t* setupHeader; unsigned setupHeaderSize;
618 getVorbisOrTheoraConfigData(track,
619 identificationHeader, identificationHeaderSize,
620 commentHeader, commentHeaderSize,
621 setupHeader, setupHeaderSize);
622
623 if (strcmp(track->mimeType, "video/THEORA") == 0) {
624 result = TheoraVideoRTPSink
625 ::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic,
626 identificationHeader, identificationHeaderSize,
627 commentHeader, commentHeaderSize,
628 setupHeader, setupHeaderSize);
629 } else { // Vorbis
630 result = VorbisAudioRTPSink
631 ::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic,
632 track->samplingFrequency, track->numChannels,
633 identificationHeader, identificationHeaderSize,
634 commentHeader, commentHeaderSize,
635 setupHeader, setupHeaderSize);
636 }
637 delete[] identificationHeader; delete[] commentHeader; delete[] setupHeader;
638 } else if (strcmp(track->mimeType, "video/RAW") == 0) {
639 result = RawVideoRTPSink::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic,
640 track->pixelWidth, track->pixelHeight, track->bitDepth, track->colorSampling, track->colorimetry);
641 } else if (strcmp(track->mimeType, "video/H264") == 0) {
642 u_int8_t* sps; unsigned spsSize;
643 u_int8_t* pps; unsigned ppsSize;
644
645 getH264ConfigData(track, sps, spsSize, pps, ppsSize);
646 result = H264VideoRTPSink::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic,
647 sps, spsSize, pps, ppsSize);
648 delete[] sps; delete[] pps;
649 } else if (strcmp(track->mimeType, "video/H265") == 0) {
650 u_int8_t* vps; unsigned vpsSize;
651 u_int8_t* sps; unsigned spsSize;
652 u_int8_t* pps; unsigned ppsSize;
653
654 getH265ConfigData(track, vps, vpsSize, sps, spsSize, pps, ppsSize);
655 result = H265VideoRTPSink::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic,
656 vps, vpsSize, sps, spsSize, pps, ppsSize);
657 delete[] vps; delete[] sps; delete[] pps;
658 } else if (strcmp(track->mimeType, "video/VP8") == 0) {
659 result = VP8VideoRTPSink::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic);
660 } else if (strcmp(track->mimeType, "video/VP9") == 0) {
661 result = VP9VideoRTPSink::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic);
662 } else if (strcmp(track->mimeType, "text/T140") == 0) {
663 result = T140TextRTPSink::createNew(envir(), rtpGroupsock, rtpPayloadTypeIfDynamic);
664 }
665 } while (0);
666
667 return result;
668 }
669
createFileSinkForTrackNumber(unsigned trackNumber,char const * fileName)670 FileSink* MatroskaFile::createFileSinkForTrackNumber(unsigned trackNumber, char const* fileName) {
671 FileSink* result = NULL; // default value, if an error occurs
672 Boolean createOggFileSink = False; // by default
673
674 do {
675 MatroskaTrack* track = lookup(trackNumber);
676 if (track == NULL) break;
677
678 if (strcmp(track->mimeType, "video/H264") == 0) {
679 u_int8_t* sps; unsigned spsSize;
680 u_int8_t* pps; unsigned ppsSize;
681
682 getH264ConfigData(track, sps, spsSize, pps, ppsSize);
683
684 char* sps_base64 = base64Encode((char*)sps, spsSize);
685 char* pps_base64 = base64Encode((char*)pps, ppsSize);
686 delete[] sps; delete[] pps;
687
688 char* sPropParameterSetsStr
689 = new char[(sps_base64 == NULL ? 0 : strlen(sps_base64)) +
690 (pps_base64 == NULL ? 0 : strlen(pps_base64)) +
691 10 /*more than enough space*/];
692 sprintf(sPropParameterSetsStr, "%s,%s", sps_base64, pps_base64);
693 delete[] sps_base64; delete[] pps_base64;
694
695 result = H264VideoFileSink::createNew(envir(), fileName,
696 sPropParameterSetsStr,
697 MAX_KEY_FRAME_SIZE); // extra large buffer size for large key frames
698 delete[] sPropParameterSetsStr;
699 } else if (strcmp(track->mimeType, "video/H265") == 0) {
700 u_int8_t* vps; unsigned vpsSize;
701 u_int8_t* sps; unsigned spsSize;
702 u_int8_t* pps; unsigned ppsSize;
703
704 getH265ConfigData(track, vps, vpsSize, sps, spsSize, pps, ppsSize);
705
706 char* vps_base64 = base64Encode((char*)vps, vpsSize);
707 char* sps_base64 = base64Encode((char*)sps, spsSize);
708 char* pps_base64 = base64Encode((char*)pps, ppsSize);
709 delete[] vps; delete[] sps; delete[] pps;
710
711 result = H265VideoFileSink::createNew(envir(), fileName,
712 vps_base64, sps_base64, pps_base64,
713 MAX_KEY_FRAME_SIZE); // extra large buffer size for large key frames
714 delete[] vps_base64; delete[] sps_base64; delete[] pps_base64;
715 } else if (strcmp(track->mimeType, "video/THEORA") == 0) {
716 createOggFileSink = True;
717 } else if (strcmp(track->mimeType, "audio/AMR") == 0 ||
718 strcmp(track->mimeType, "audio/AMR-WB") == 0) {
719 // For AMR audio streams, we use a special sink that inserts AMR frame hdrs:
720 result = AMRAudioFileSink::createNew(envir(), fileName);
721 } else if (strcmp(track->mimeType, "audio/VORBIS") == 0 ||
722 strcmp(track->mimeType, "audio/OPUS") == 0) {
723 createOggFileSink = True;
724 }
725
726 if (createOggFileSink) {
727 char* configStr = NULL; // by default
728
729 if (strcmp(track->mimeType, "audio/VORBIS") == 0 || strcmp(track->mimeType, "video/THEORA") == 0) {
730 u_int8_t* identificationHeader; unsigned identificationHeaderSize;
731 u_int8_t* commentHeader; unsigned commentHeaderSize;
732 u_int8_t* setupHeader; unsigned setupHeaderSize;
733 getVorbisOrTheoraConfigData(track,
734 identificationHeader, identificationHeaderSize,
735 commentHeader, commentHeaderSize,
736 setupHeader, setupHeaderSize);
737 u_int32_t identField = 0xFACADE; // Can we get a real value from the file somehow?
738 configStr = generateVorbisOrTheoraConfigStr(identificationHeader, identificationHeaderSize,
739 commentHeader, commentHeaderSize,
740 setupHeader, setupHeaderSize,
741 identField);
742 delete[] identificationHeader; delete[] commentHeader; delete[] setupHeader;
743 }
744
745 result = OggFileSink::createNew(envir(), fileName, track->samplingFrequency, configStr, MAX_KEY_FRAME_SIZE);
746 delete[] configStr;
747 } else if (result == NULL) {
748 // By default, just create a regular "FileSink":
749 result = FileSink::createNew(envir(), fileName, MAX_KEY_FRAME_SIZE);
750 }
751 } while (0);
752
753 return result;
754 }
755
addTrack(MatroskaTrack * newTrack,unsigned trackNumber)756 void MatroskaFile::addTrack(MatroskaTrack* newTrack, unsigned trackNumber) {
757 fTrackTable->add(newTrack, trackNumber);
758 }
759
addCuePoint(double cueTime,u_int64_t clusterOffsetInFile,unsigned blockNumWithinCluster)760 void MatroskaFile::addCuePoint(double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster) {
761 Boolean dummy = False; // not used
762 CuePoint::addCuePoint(fCuePoints, cueTime, clusterOffsetInFile, blockNumWithinCluster, dummy);
763 }
764
lookupCuePoint(double & cueTime,u_int64_t & resultClusterOffsetInFile,unsigned & resultBlockNumWithinCluster)765 Boolean MatroskaFile::lookupCuePoint(double& cueTime, u_int64_t& resultClusterOffsetInFile, unsigned& resultBlockNumWithinCluster) {
766 if (fCuePoints == NULL) return False;
767
768 (void)fCuePoints->lookup(cueTime, resultClusterOffsetInFile, resultBlockNumWithinCluster);
769 return True;
770 }
771
printCuePoints(FILE * fid)772 void MatroskaFile::printCuePoints(FILE* fid) {
773 CuePoint::fprintf(fid, fCuePoints);
774 }
775
776
777 ////////// MatroskaTrackTable implementation //////////
778
MatroskaTrackTable()779 MatroskaTrackTable::MatroskaTrackTable()
780 : fTable(HashTable::create(ONE_WORD_HASH_KEYS)) {
781 }
782
~MatroskaTrackTable()783 MatroskaTrackTable::~MatroskaTrackTable() {
784 // Remove and delete all of our "MatroskaTrack" descriptors, and the hash table itself:
785 MatroskaTrack* track;
786 while ((track = (MatroskaTrack*)fTable->RemoveNext()) != NULL) {
787 delete track;
788 }
789 delete fTable;
790 }
791
add(MatroskaTrack * newTrack,unsigned trackNumber)792 void MatroskaTrackTable::add(MatroskaTrack* newTrack, unsigned trackNumber) {
793 if (newTrack != NULL && newTrack->trackNumber != 0) fTable->Remove((char const*)newTrack->trackNumber);
794 MatroskaTrack* existingTrack = (MatroskaTrack*)fTable->Add((char const*)trackNumber, newTrack);
795 delete existingTrack; // in case it wasn't NULL
796 }
797
lookup(unsigned trackNumber)798 MatroskaTrack* MatroskaTrackTable::lookup(unsigned trackNumber) {
799 return (MatroskaTrack*)fTable->Lookup((char const*)trackNumber);
800 }
801
numTracks() const802 unsigned MatroskaTrackTable::numTracks() const { return fTable->numEntries(); }
803
Iterator(MatroskaTrackTable & ourTable)804 MatroskaTrackTable::Iterator::Iterator(MatroskaTrackTable& ourTable) {
805 fIter = HashTable::Iterator::create(*(ourTable.fTable));
806 }
807
~Iterator()808 MatroskaTrackTable::Iterator::~Iterator() {
809 delete fIter;
810 }
811
next()812 MatroskaTrack* MatroskaTrackTable::Iterator::next() {
813 char const* key;
814 return (MatroskaTrack*)fIter->next(key);
815 }
816
817
818 ////////// MatroskaTrack implementation //////////
819
MatroskaTrack()820 MatroskaTrack::MatroskaTrack()
821 : trackNumber(0/*not set*/), trackType(0/*unknown*/),
822 isEnabled(True), isDefault(True), isForced(False),
823 defaultDuration(0),
824 name(NULL), language(NULL), codecID(NULL),
825 samplingFrequency(0), numChannels(2), mimeType(""),
826 codecPrivateSize(0), codecPrivate(NULL),
827 codecPrivateUsesH264FormatForH265(False), codecIsOpus(False),
828 headerStrippedBytesSize(0), headerStrippedBytes(NULL),
829 colorSampling(""), colorimetry("BT709-2") /*Matroska default value for Primaries */,
830 pixelWidth(0), pixelHeight(0), bitDepth(8), subframeSizeSize(0) {
831 }
832
~MatroskaTrack()833 MatroskaTrack::~MatroskaTrack() {
834 delete[] name; delete[] language; delete[] codecID;
835 delete[] codecPrivate;
836 delete[] headerStrippedBytes;
837 }
838
839
840 ////////// MatroskaDemux implementation //////////
841
MatroskaDemux(MatroskaFile & ourFile)842 MatroskaDemux::MatroskaDemux(MatroskaFile& ourFile)
843 : Medium(ourFile.envir()),
844 fOurFile(ourFile), fDemuxedTracksTable(HashTable::create(ONE_WORD_HASH_KEYS)),
845 fNextTrackTypeToCheck(0x1) {
846 fOurParser = new MatroskaFileParser(ourFile, ByteStreamFileSource::createNew(envir(), ourFile.fileName()),
847 handleEndOfFile, this, this);
848 }
849
~MatroskaDemux()850 MatroskaDemux::~MatroskaDemux() {
851 // Begin by acting as if we've reached the end of the source file. This should cause all of our demuxed tracks to get closed.
852 handleEndOfFile();
853
854 // Then delete our table of "MatroskaDemuxedTrack"s
855 // - but not the "MatroskaDemuxedTrack"s themselves; that should have already happened:
856 delete fDemuxedTracksTable;
857
858 delete fOurParser;
859 fOurFile.removeDemux(this);
860 }
861
newDemuxedTrack()862 FramedSource* MatroskaDemux::newDemuxedTrack() {
863 unsigned dummyResultTrackNumber;
864 return newDemuxedTrack(dummyResultTrackNumber);
865 }
866
newDemuxedTrack(unsigned & resultTrackNumber)867 FramedSource* MatroskaDemux::newDemuxedTrack(unsigned& resultTrackNumber) {
868 FramedSource* result;
869 resultTrackNumber = 0;
870
871 for (result = NULL; result == NULL && fNextTrackTypeToCheck != MATROSKA_TRACK_TYPE_OTHER;
872 fNextTrackTypeToCheck <<= 1) {
873 if (fNextTrackTypeToCheck == MATROSKA_TRACK_TYPE_VIDEO) resultTrackNumber = fOurFile.chosenVideoTrackNumber();
874 else if (fNextTrackTypeToCheck == MATROSKA_TRACK_TYPE_AUDIO) resultTrackNumber = fOurFile.chosenAudioTrackNumber();
875 else if (fNextTrackTypeToCheck == MATROSKA_TRACK_TYPE_SUBTITLE) resultTrackNumber = fOurFile.chosenSubtitleTrackNumber();
876
877 result = newDemuxedTrackByTrackNumber(resultTrackNumber);
878 }
879
880 return result;
881 }
882
newDemuxedTrackByTrackNumber(unsigned trackNumber)883 FramedSource* MatroskaDemux::newDemuxedTrackByTrackNumber(unsigned trackNumber) {
884 if (trackNumber == 0) return NULL;
885
886 FramedSource* trackSource = new MatroskaDemuxedTrack(envir(), trackNumber, *this);
887 fDemuxedTracksTable->Add((char const*)trackNumber, trackSource);
888 return trackSource;
889 }
890
lookupDemuxedTrack(unsigned trackNumber)891 MatroskaDemuxedTrack* MatroskaDemux::lookupDemuxedTrack(unsigned trackNumber) {
892 return (MatroskaDemuxedTrack*)fDemuxedTracksTable->Lookup((char const*)trackNumber);
893 }
894
removeTrack(unsigned trackNumber)895 void MatroskaDemux::removeTrack(unsigned trackNumber) {
896 fDemuxedTracksTable->Remove((char const*)trackNumber);
897 if (fDemuxedTracksTable->numEntries() == 0) {
898 // We no longer have any demuxed tracks, so delete ourselves now:
899 Medium::close(this);
900 }
901 }
902
continueReading()903 void MatroskaDemux::continueReading() {
904 fOurParser->continueParsing();
905 }
906
seekToTime(double & seekNPT)907 void MatroskaDemux::seekToTime(double& seekNPT) {
908 if (fOurParser != NULL) fOurParser->seekToTime(seekNPT);
909 }
910
pause()911 void MatroskaDemux::pause() {
912 if (fOurParser != NULL) fOurParser->pause();
913 }
914
handleEndOfFile(void * clientData)915 void MatroskaDemux::handleEndOfFile(void* clientData) {
916 ((MatroskaDemux*)clientData)->handleEndOfFile();
917 }
918
handleEndOfFile()919 void MatroskaDemux::handleEndOfFile() {
920 // Iterate through all of our 'demuxed tracks', handling 'end of input' on each one.
921 // Hack: Because this can cause the hash table to get modified underneath us, we don't call the handlers until after we've
922 // first iterated through all of the tracks.
923 unsigned numTracks = fDemuxedTracksTable->numEntries();
924 if (numTracks == 0) return;
925 MatroskaDemuxedTrack** tracks = new MatroskaDemuxedTrack*[numTracks];
926
927 HashTable::Iterator* iter = HashTable::Iterator::create(*fDemuxedTracksTable);
928 unsigned i;
929 char const* trackNumber;
930
931 for (i = 0; i < numTracks; ++i) {
932 tracks[i] = (MatroskaDemuxedTrack*)iter->next(trackNumber);
933 }
934 delete iter;
935
936 for (i = 0; i < numTracks; ++i) {
937 if (tracks[i] == NULL) continue; // sanity check; shouldn't happen
938 tracks[i]->handleClosure();
939 }
940
941 delete[] tracks;
942 }
943
resetState()944 void MatroskaDemux::resetState() {
945 // Iterate through all of our 'demuxed tracks', calling 'reset()' on each one.
946 HashTable::Iterator* iter = HashTable::Iterator::create(*fDemuxedTracksTable);
947 MatroskaDemuxedTrack* demuxedTrack;
948 char const* trackNumber;
949
950 while ((demuxedTrack = (MatroskaDemuxedTrack*)iter->next(trackNumber)) != NULL) {
951 demuxedTrack->reset();
952 }
953 delete iter;
954 }
955
956
957 ////////// CuePoint implementation //////////
958
CuePoint(double cueTime,u_int64_t clusterOffsetInFile,unsigned blockNumWithinCluster)959 CuePoint::CuePoint(double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster)
960 : fBalance(0),
961 fCueTime(cueTime), fClusterOffsetInFile(clusterOffsetInFile), fBlockNumWithinCluster(blockNumWithinCluster - 1) {
962 fSubTree[0] = fSubTree[1] = NULL;
963 }
964
~CuePoint()965 CuePoint::~CuePoint() {
966 delete fSubTree[0]; delete fSubTree[1];
967 }
968
addCuePoint(CuePoint * & root,double cueTime,u_int64_t clusterOffsetInFile,unsigned blockNumWithinCluster,Boolean & needToReviseBalanceOfParent)969 void CuePoint::addCuePoint(CuePoint*& root, double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster,
970 Boolean& needToReviseBalanceOfParent) {
971 needToReviseBalanceOfParent = False; // by default; may get changed below
972
973 if (root == NULL) {
974 root = new CuePoint(cueTime, clusterOffsetInFile, blockNumWithinCluster);
975 needToReviseBalanceOfParent = True;
976 } else if (cueTime == root->fCueTime) {
977 // Replace existing data:
978 root->fClusterOffsetInFile = clusterOffsetInFile;
979 root->fBlockNumWithinCluster = blockNumWithinCluster - 1;
980 } else {
981 // Add to our left or right subtree:
982 int direction = cueTime > root->fCueTime; // 0 (left) or 1 (right)
983 Boolean needToReviseOurBalance = False;
984 addCuePoint(root->fSubTree[direction], cueTime, clusterOffsetInFile, blockNumWithinCluster, needToReviseOurBalance);
985
986 if (needToReviseOurBalance) {
987 // We need to change our 'balance' number, perhaps while also performing a rotation to bring ourself back into balance:
988 if (root->fBalance == 0) {
989 // We were balanced before, but now we're unbalanced (by 1) on the "direction" side:
990 root->fBalance = -1 + 2*direction; // -1 for "direction" 0; 1 for "direction" 1
991 needToReviseBalanceOfParent = True;
992 } else if (root->fBalance == 1 - 2*direction) { // 1 for "direction" 0; -1 for "direction" 1
993 // We were unbalanced (by 1) on the side opposite to where we added an entry, so now we're balanced:
994 root->fBalance = 0;
995 } else {
996 // We were unbalanced (by 1) on the side where we added an entry, so now we're unbalanced by 2, and have to rebalance:
997 if (root->fSubTree[direction]->fBalance == -1 + 2*direction) { // -1 for "direction" 0; 1 for "direction" 1
998 // We're 'doubly-unbalanced' on this side, so perform a single rotation in the opposite direction:
999 root->fBalance = root->fSubTree[direction]->fBalance = 0;
1000 rotate(1-direction, root);
1001 } else {
1002 // This is the Left-Right case (for "direction" 0) or the Right-Left case (for "direction" 1); perform two rotations:
1003 char newParentCurBalance = root->fSubTree[direction]->fSubTree[1-direction]->fBalance;
1004 if (newParentCurBalance == 1 - 2*direction) { // 1 for "direction" 0; -1 for "direction" 1
1005 root->fBalance = 0;
1006 root->fSubTree[direction]->fBalance = -1 + 2*direction; // -1 for "direction" 0; 1 for "direction" 1
1007 } else if (newParentCurBalance == 0) {
1008 root->fBalance = 0;
1009 root->fSubTree[direction]->fBalance = 0;
1010 } else {
1011 root->fBalance = 1 - 2*direction; // 1 for "direction" 0; -1 for "direction" 1
1012 root->fSubTree[direction]->fBalance = 0;
1013 }
1014 rotate(direction, root->fSubTree[direction]);
1015
1016 root->fSubTree[direction]->fBalance = 0; // the new root will be balanced
1017 rotate(1-direction, root);
1018 }
1019 }
1020 }
1021 }
1022 }
1023
lookup(double & cueTime,u_int64_t & resultClusterOffsetInFile,unsigned & resultBlockNumWithinCluster)1024 Boolean CuePoint::lookup(double& cueTime, u_int64_t& resultClusterOffsetInFile, unsigned& resultBlockNumWithinCluster) {
1025 if (cueTime < fCueTime) {
1026 if (left() == NULL) {
1027 resultClusterOffsetInFile = 0;
1028 resultBlockNumWithinCluster = 0;
1029 return False;
1030 } else {
1031 return left()->lookup(cueTime, resultClusterOffsetInFile, resultBlockNumWithinCluster);
1032 }
1033 } else {
1034 if (right() == NULL || !right()->lookup(cueTime, resultClusterOffsetInFile, resultBlockNumWithinCluster)) {
1035 // Use this record:
1036 cueTime = fCueTime;
1037 resultClusterOffsetInFile = fClusterOffsetInFile;
1038 resultBlockNumWithinCluster = fBlockNumWithinCluster;
1039 }
1040 return True;
1041 }
1042 }
1043
fprintf(FILE * fid,CuePoint * cuePoint)1044 void CuePoint::fprintf(FILE* fid, CuePoint* cuePoint) {
1045 if (cuePoint != NULL) {
1046 ::fprintf(fid, "[");
1047 fprintf(fid, cuePoint->left());
1048
1049 ::fprintf(fid, ",%.1f{%d},", cuePoint->fCueTime, cuePoint->fBalance);
1050
1051 fprintf(fid, cuePoint->right());
1052 ::fprintf(fid, "]");
1053 }
1054 }
1055
rotate(unsigned direction,CuePoint * & root)1056 void CuePoint::rotate(unsigned direction/*0 => left; 1 => right*/, CuePoint*& root) {
1057 CuePoint* pivot = root->fSubTree[1-direction]; // ASSERT: pivot != NULL
1058 root->fSubTree[1-direction] = pivot->fSubTree[direction];
1059 pivot->fSubTree[direction] = root;
1060 root = pivot;
1061 }
1062