1/**********
2This library is free software; you can redistribute it and/or modify it under
3the terms of the GNU Lesser General Public License as published by the
4Free Software Foundation; either version 3 of the License, or (at your
5option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6
7This library is distributed in the hope that it will be useful, but WITHOUT
8ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10more details.
11
12You should have received a copy of the GNU Lesser General Public License
13along with this library; if not, write to the Free Software Foundation, Inc.,
1451 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
46class CuePoint {
47public:
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
60private:
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
63 CuePoint* left() const { return fSubTree[0]; }
64 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
74UsageEnvironment& 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:
80class MatroskaTrackTable {
81public:
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
99private:
100 friend class Iterator;
101 HashTable* fTable;
102};
103
104
105
106////////// MatroskaFile implementation //////////
107
108void MatroskaFile
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
114MatroskaFile::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
135MatroskaFile::~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
151void MatroskaFile::handleEndOfTrackHeaderParsing(void* clientData) {
152 ((MatroskaFile*)clientData)->handleEndOfTrackHeaderParsing();
153}
154
155class TrackChoiceRecord {
156public:
157 unsigned trackNumber;
158 u_int8_t trackType;
159 unsigned choiceFlags;
160};
161
162void 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
232MatroskaTrack* MatroskaFile::lookup(unsigned trackNumber) const {
233 return fTrackTable->lookup(trackNumber);
234}
235
236MatroskaDemux* MatroskaFile::newDemux() {
237 MatroskaDemux* demux = new MatroskaDemux(*this);
238 fDemuxesTable->Add((char const*)demux, demux);
239
240 return demux;
241}
242
243void 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
251void 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
309void 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
412void MatroskaFile
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
511float 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
520FramedSource* MatroskaFile
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
572char const* MatroskaFile::trackMIMEType(unsigned trackNumber) const {
573 MatroskaTrack* track = lookup(trackNumber);
574 if (track == NULL) return NULL;
575
576 return track->mimeType;
577}
578
579RTPSink* MatroskaFile
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->pixelHeight, track->pixelWidth, 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
670FileSink* 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
756void MatroskaFile::addTrack(MatroskaTrack* newTrack, unsigned trackNumber) {
757 fTrackTable->add(newTrack, trackNumber);
758}
759
760void 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
765Boolean 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
772void MatroskaFile::printCuePoints(FILE* fid) {
773 CuePoint::fprintf(fid, fCuePoints);
774}
775
776
777////////// MatroskaTrackTable implementation //////////
778
779MatroskaTrackTable::MatroskaTrackTable()
780 : fTable(HashTable::create(ONE_WORD_HASH_KEYS)) {
781}
782
783MatroskaTrackTable::~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
792void 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
798MatroskaTrack* MatroskaTrackTable::lookup(unsigned trackNumber) {
799 return (MatroskaTrack*)fTable->Lookup((char const*)trackNumber);
800}
801
802unsigned MatroskaTrackTable::numTracks() const { return fTable->numEntries(); }
803
804MatroskaTrackTable::Iterator::Iterator(MatroskaTrackTable& ourTable) {
805 fIter = HashTable::Iterator::create(*(ourTable.fTable));
806}
807
808MatroskaTrackTable::Iterator::~Iterator() {
809 delete fIter;
810}
811
812MatroskaTrack* MatroskaTrackTable::Iterator::next() {
813 char const* key;
814 return (MatroskaTrack*)fIter->next(key);
815}
816
817
818////////// MatroskaTrack implementation //////////
819
820MatroskaTrack::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
833MatroskaTrack::~MatroskaTrack() {
834 delete[] name; delete[] language; delete[] codecID;
835 delete[] codecPrivate;
836 delete[] headerStrippedBytes;
837}
838
839
840////////// MatroskaDemux implementation //////////
841
842MatroskaDemux::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
850MatroskaDemux::~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
862FramedSource* MatroskaDemux::newDemuxedTrack() {
863 unsigned dummyResultTrackNumber;
864 return newDemuxedTrack(dummyResultTrackNumber);
865}
866
867FramedSource* 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
883FramedSource* 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
891MatroskaDemuxedTrack* MatroskaDemux::lookupDemuxedTrack(unsigned trackNumber) {
892 return (MatroskaDemuxedTrack*)fDemuxedTracksTable->Lookup((char const*)trackNumber);
893}
894
895void 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
903void MatroskaDemux::continueReading() {
904 fOurParser->continueParsing();
905}
906
907void MatroskaDemux::seekToTime(double& seekNPT) {
908 if (fOurParser != NULL) fOurParser->seekToTime(seekNPT);
909}
910
911void MatroskaDemux::handleEndOfFile(void* clientData) {
912 ((MatroskaDemux*)clientData)->handleEndOfFile();
913}
914
915void MatroskaDemux::handleEndOfFile() {
916 // Iterate through all of our 'demuxed tracks', handling 'end of input' on each one.
917 // Hack: Because this can cause the hash table to get modified underneath us, we don't call the handlers until after we've
918 // first iterated through all of the tracks.
919 unsigned numTracks = fDemuxedTracksTable->numEntries();
920 if (numTracks == 0) return;
921 MatroskaDemuxedTrack** tracks = new MatroskaDemuxedTrack*[numTracks];
922
923 HashTable::Iterator* iter = HashTable::Iterator::create(*fDemuxedTracksTable);
924 unsigned i;
925 char const* trackNumber;
926
927 for (i = 0; i < numTracks; ++i) {
928 tracks[i] = (MatroskaDemuxedTrack*)iter->next(trackNumber);
929 }
930 delete iter;
931
932 for (i = 0; i < numTracks; ++i) {
933 if (tracks[i] == NULL) continue; // sanity check; shouldn't happen
934 tracks[i]->handleClosure();
935 }
936
937 delete[] tracks;
938}
939
940
941////////// CuePoint implementation //////////
942
943CuePoint::CuePoint(double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster)
944 : fBalance(0),
945 fCueTime(cueTime), fClusterOffsetInFile(clusterOffsetInFile), fBlockNumWithinCluster(blockNumWithinCluster - 1) {
946 fSubTree[0] = fSubTree[1] = NULL;
947}
948
949CuePoint::~CuePoint() {
950 delete fSubTree[0]; delete fSubTree[1];
951}
952
953void CuePoint::addCuePoint(CuePoint*& root, double cueTime, u_int64_t clusterOffsetInFile, unsigned blockNumWithinCluster,
954 Boolean& needToReviseBalanceOfParent) {
955 needToReviseBalanceOfParent = False; // by default; may get changed below
956
957 if (root == NULL) {
958 root = new CuePoint(cueTime, clusterOffsetInFile, blockNumWithinCluster);
959 needToReviseBalanceOfParent = True;
960 } else if (cueTime == root->fCueTime) {
961 // Replace existing data:
962 root->fClusterOffsetInFile = clusterOffsetInFile;
963 root->fBlockNumWithinCluster = blockNumWithinCluster - 1;
964 } else {
965 // Add to our left or right subtree:
966 int direction = cueTime > root->fCueTime; // 0 (left) or 1 (right)
967 Boolean needToReviseOurBalance = False;
968 addCuePoint(root->fSubTree[direction], cueTime, clusterOffsetInFile, blockNumWithinCluster, needToReviseOurBalance);
969
970 if (needToReviseOurBalance) {
971 // We need to change our 'balance' number, perhaps while also performing a rotation to bring ourself back into balance:
972 if (root->fBalance == 0) {
973 // We were balanced before, but now we're unbalanced (by 1) on the "direction" side:
974 root->fBalance = -1 + 2*direction; // -1 for "direction" 0; 1 for "direction" 1
975 needToReviseBalanceOfParent = True;
976 } else if (root->fBalance == 1 - 2*direction) { // 1 for "direction" 0; -1 for "direction" 1
977 // We were unbalanced (by 1) on the side opposite to where we added an entry, so now we're balanced:
978 root->fBalance = 0;
979 } else {
980 // We were unbalanced (by 1) on the side where we added an entry, so now we're unbalanced by 2, and have to rebalance:
981 if (root->fSubTree[direction]->fBalance == -1 + 2*direction) { // -1 for "direction" 0; 1 for "direction" 1
982 // We're 'doubly-unbalanced' on this side, so perform a single rotation in the opposite direction:
983 root->fBalance = root->fSubTree[direction]->fBalance = 0;
984 rotate(1-direction, root);
985 } else {
986 // This is the Left-Right case (for "direction" 0) or the Right-Left case (for "direction" 1); perform two rotations:
987 char newParentCurBalance = root->fSubTree[direction]->fSubTree[1-direction]->fBalance;
988 if (newParentCurBalance == 1 - 2*direction) { // 1 for "direction" 0; -1 for "direction" 1
989 root->fBalance = 0;
990 root->fSubTree[direction]->fBalance = -1 + 2*direction; // -1 for "direction" 0; 1 for "direction" 1
991 } else if (newParentCurBalance == 0) {
992 root->fBalance = 0;
993 root->fSubTree[direction]->fBalance = 0;
994 } else {
995 root->fBalance = 1 - 2*direction; // 1 for "direction" 0; -1 for "direction" 1
996 root->fSubTree[direction]->fBalance = 0;
997 }
998 rotate(direction, root->fSubTree[direction]);
999
1000 root->fSubTree[direction]->fBalance = 0; // the new root will be balanced
1001 rotate(1-direction, root);
1002 }
1003 }
1004 }
1005 }
1006}
1007
1008Boolean CuePoint::lookup(double& cueTime, u_int64_t& resultClusterOffsetInFile, unsigned& resultBlockNumWithinCluster) {
1009 if (cueTime < fCueTime) {
1010 if (left() == NULL) {
1011 resultClusterOffsetInFile = 0;
1012 resultBlockNumWithinCluster = 0;
1013 return False;
1014 } else {
1015 return left()->lookup(cueTime, resultClusterOffsetInFile, resultBlockNumWithinCluster);
1016 }
1017 } else {
1018 if (right() == NULL || !right()->lookup(cueTime, resultClusterOffsetInFile, resultBlockNumWithinCluster)) {
1019 // Use this record:
1020 cueTime = fCueTime;
1021 resultClusterOffsetInFile = fClusterOffsetInFile;
1022 resultBlockNumWithinCluster = fBlockNumWithinCluster;
1023 }
1024 return True;
1025 }
1026}
1027
1028void CuePoint::fprintf(FILE* fid, CuePoint* cuePoint) {
1029 if (cuePoint != NULL) {
1030 ::fprintf(fid, "[");
1031 fprintf(fid, cuePoint->left());
1032
1033 ::fprintf(fid, ",%.1f{%d},", cuePoint->fCueTime, cuePoint->fBalance);
1034
1035 fprintf(fid, cuePoint->right());
1036 ::fprintf(fid, "]");
1037 }
1038}
1039
1040void CuePoint::rotate(unsigned direction/*0 => left; 1 => right*/, CuePoint*& root) {
1041 CuePoint* pivot = root->fSubTree[1-direction]; // ASSERT: pivot != NULL
1042 root->fSubTree[1-direction] = pivot->fSubTree[direction];
1043 pivot->fSubTree[direction] = root;
1044 root = pivot;
1045}
1046