1/**************************************************************************** 2** libebml : parse EBML files, see http://embl.sourceforge.net/ 3** 4** <file/class description> 5** 6** Copyright (C) 2002-2005 Steve Lhomme. All rights reserved. 7** 8** This library is free software; you can redistribute it and/or 9** modify it under the terms of the GNU Lesser General Public 10** License as published by the Free Software Foundation; either 11** version 2.1 of the License, or (at your option) any later version. 12** 13** This library is distributed in the hope that it will be useful, 14** but WITHOUT ANY WARRANTY; without even the implied warranty of 15** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16** Lesser General Public License for more details. 17** 18** You should have received a copy of the GNU Lesser General Public 19** License along with this library; if not, write to the Free Software 20** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 21** 22** See http://www.matroska.org/license/lgpl/ for LGPL licensing information. 23** 24** Contact license@matroska.org if any conditions of this licensing are 25** not clear to you. 26** 27**********************************************************************/ 28 29/*! 30 \file 31 \version \$Id: EbmlElement.cpp 1232 2005-10-15 15:56:52Z robux4 $ 32 \author Steve Lhomme <robux4 @ users.sf.net> 33*/ 34 35#include <cassert> 36 37#include "ebml/EbmlElement.h" 38#include "ebml/EbmlMaster.h" 39#include "ebml/EbmlStream.h" 40#include "ebml/EbmlVoid.h" 41#include "ebml/EbmlDummy.h" 42#include "ebml/EbmlContexts.h" 43 44START_LIBEBML_NAMESPACE 45 46/*! 47 \todo handle more than CodedSize of 5 48*/ 49int CodedSizeLength(uint64 Length, unsigned int SizeLength, bool bSizeFinite) 50{ 51 int CodedSize; 52 if (bSizeFinite) { 53 // prepare the head of the size (000...01xxxxxx) 54 // optimal size 55 if (Length < 127) // 2^7 - 1 56 CodedSize = 1; 57 else if (Length < 16383) // 2^14 - 1 58 CodedSize = 2; 59 else if (Length < 2097151L) // 2^21 - 1 60 CodedSize = 3; 61 else if (Length < 268435455L) // 2^28 - 1 62 CodedSize = 4; 63 else CodedSize = 5; 64 } else { 65 if (Length <= 127) // 2^7 - 1 66 CodedSize = 1; 67 else if (Length <= 16383) // 2^14 - 1 68 CodedSize = 2; 69 else if (Length <= 2097151L) // 2^21 - 1 70 CodedSize = 3; 71 else if (Length <= 268435455L) // 2^28 - 1 72 CodedSize = 4; 73 else CodedSize = 5; 74 } 75 76 if (SizeLength > 0 && CodedSize < SizeLength) { 77 // defined size 78 CodedSize = SizeLength; 79 } 80 81 return CodedSize; 82} 83 84/*! 85 \todo handle more than CodedSize of 5 86*/ 87int CodedSizeLengthSigned(int64 Length, unsigned int SizeLength) 88{ 89 unsigned int CodedSize; 90 // prepare the head of the size (000...01xxxxxx) 91 // optimal size 92 if (Length > -64 && Length < 64) // 2^6 93 CodedSize = 1; 94 else if (Length > -8192 && Length < 8192) // 2^13 95 CodedSize = 2; 96 else if (Length > -1048576L && Length < 1048576L) // 2^20 97 CodedSize = 3; 98 else if (Length > -134217728L && Length < 134217728L) // 2^27 99 CodedSize = 4; 100 else CodedSize = 5; 101 102 if (SizeLength > 0 && CodedSize < SizeLength) { 103 // defined size 104 CodedSize = SizeLength; 105 } 106 107 return CodedSize; 108} 109 110int CodedValueLength(uint64 Length, int CodedSize, binary * OutBuffer) 111{ 112 int _SizeMask = 0xFF; 113 OutBuffer[0] = 1 << (8 - CodedSize); 114 for (int i=1; i<CodedSize; i++) { 115 OutBuffer[CodedSize-i] = Length & 0xFF; 116 Length >>= 8; 117 _SizeMask >>= 1; 118 } 119 // first one use a OR with the "EBML size head" 120 OutBuffer[0] |= Length & 0xFF & _SizeMask; 121 return CodedSize; 122} 123 124int CodedValueLengthSigned(int64 Length, int CodedSize, binary * OutBuffer) 125{ 126 if (Length > -64 && Length < 64) // 2^6 127 Length += 63; 128 else if (Length > -8192 && Length < 8192) // 2^13 129 Length += 8191; 130 else if (Length > -1048576L && Length < 1048576L) // 2^20 131 Length += 1048575L; 132 else if (Length > -134217728L && Length < 134217728L) // 2^27 133 Length += 134217727L; 134 135 return CodedValueLength(Length, CodedSize, OutBuffer); 136} 137 138uint64 ReadCodedSizeValue(const binary * InBuffer, uint32 & BufferSize, uint64 & SizeUnknown) 139{ 140 binary SizeBitMask = 1 << 7; 141 uint64 Result = 0x7F; 142 unsigned int SizeIdx, PossibleSizeLength = 0; 143 binary PossibleSize[8]; 144 145 SizeUnknown = 0x7F; // the last bit is discarded when computing the size 146 for (SizeIdx = 0; SizeIdx < BufferSize && SizeIdx < 8; SizeIdx++) { 147 if (InBuffer[0] & (SizeBitMask >> SizeIdx)) { 148 // ID found 149 PossibleSizeLength = SizeIdx + 1; 150 SizeBitMask >>= SizeIdx; 151 for (SizeIdx = 0; SizeIdx < PossibleSizeLength; SizeIdx++) { 152 PossibleSize[SizeIdx] = InBuffer[SizeIdx]; 153 } 154 for (SizeIdx = 0; SizeIdx < PossibleSizeLength - 1; SizeIdx++) { 155 Result <<= 7; 156 Result |= 0xFF; 157 } 158 159 Result = 0; 160 Result |= PossibleSize[0] & ~SizeBitMask; 161 for (unsigned int i = 1; i<PossibleSizeLength; i++) { 162 Result <<= 8; 163 Result |= PossibleSize[i]; 164 } 165 166 BufferSize = PossibleSizeLength; 167 168 return Result; 169 } 170 SizeUnknown <<= 7; 171 SizeUnknown |= 0xFF; 172 } 173 174 BufferSize = 0; 175 return 0; 176} 177 178int64 ReadCodedSizeSignedValue(const binary * InBuffer, uint32 & BufferSize, uint64 & SizeUnknown) 179{ 180 int64 Result = ReadCodedSizeValue(InBuffer, BufferSize, SizeUnknown); 181 182 if (BufferSize != 0) 183 { 184 switch (BufferSize) 185 { 186 case 1: 187 Result -= 63; 188 break; 189 case 2: 190 Result -= 8191; 191 break; 192 case 3: 193 Result -= 1048575L; 194 break; 195 case 4: 196 Result -= 134217727L; 197 break; 198 } 199 } 200 201 return Result; 202} 203 204EbmlElement::EbmlElement(const uint64 aDefaultSize, bool bValueSet) 205 :DefaultSize(aDefaultSize) 206 ,SizeLength(0) ///< write optimal size by default 207 ,bSizeIsFinite(true) 208 ,ElementPosition(0) 209 ,SizePosition(0) 210 ,bValueIsSet(bValueSet) 211 ,DefaultIsSet(false) 212 ,bLocked(false) 213{ 214 Size = DefaultSize; 215} 216 217EbmlElement::EbmlElement(const EbmlElement & ElementToClone) 218 :Size(ElementToClone.Size) 219 ,DefaultSize(ElementToClone.DefaultSize) 220 ,SizeLength(ElementToClone.SizeLength) 221 ,bSizeIsFinite(ElementToClone.bSizeIsFinite) 222 ,ElementPosition(ElementToClone.ElementPosition) 223 ,SizePosition(ElementToClone.SizePosition) 224 ,bValueIsSet(ElementToClone.bValueIsSet) 225 ,DefaultIsSet(ElementToClone.DefaultIsSet) 226 ,bLocked(ElementToClone.bLocked) 227{ 228} 229 230/*! 231 \todo this method is deprecated and should be called FindThisID 232 \todo replace the new RawElement with the appropriate class (when known) 233*/ 234EbmlElement * EbmlElement::FindNextID(IOCallback & DataStream, const EbmlCallbacks & ClassInfos, const uint64 MaxDataSize) 235{ 236 binary PossibleId[4]; 237 int PossibleID_Length = 0; 238 binary PossibleSize[8]; // we don't support size stored in more than 64 bits 239 uint32 PossibleSizeLength = 0; 240 uint64 SizeUnknown; 241 uint64 SizeFound; 242 bool bElementFound = false; 243 244 binary BitMask; 245 uint64 aElementPosition, aSizePosition; 246 while (!bElementFound) { 247 // read ID 248 aElementPosition = DataStream.getFilePointer(); 249 uint32 ReadSize = 0; 250 BitMask = 1 << 7; 251 while (1) { 252 ReadSize += DataStream.read(&PossibleId[PossibleID_Length], 1); 253 if (ReadSize == uint32(PossibleID_Length)) { 254 return NULL; // no more data ? 255 } 256 if (++PossibleID_Length > 4) { 257 return NULL; // we don't support element IDs over class D 258 } 259 if (PossibleId[0] & BitMask) { 260 // this is the last octet of the ID 261 // check whether that's the one we're looking for 262/* if (PossibleID == ClassInfos.GlobalId) { 263 break; 264 } else { 265 /// \todo This element should be skipped (use a context ?) 266 }*/ 267 bElementFound = true; /// \todo not exactly the one we're looking for 268 break; 269 } 270 BitMask >>= 1; 271 } 272 273 // read the data size 274 aSizePosition = DataStream.getFilePointer(); 275 uint32 _SizeLength; 276 do { 277 if (PossibleSizeLength >= 8) 278 // Size is larger than 8 bytes 279 return NULL; 280 281 ReadSize += DataStream.read(&PossibleSize[PossibleSizeLength++], 1); 282 _SizeLength = PossibleSizeLength; 283 SizeFound = ReadCodedSizeValue(&PossibleSize[0], _SizeLength, SizeUnknown); 284 } while (_SizeLength == 0); 285 } 286 287 EbmlElement *Result = NULL; 288 EbmlId PossibleID(PossibleId, PossibleID_Length); 289 if (PossibleID == ClassInfos.GlobalId) { 290 // the element is the one expected 291 Result = &ClassInfos.Create(); 292 } else { 293 /// \todo find the element in the context 294 Result = new EbmlDummy(PossibleID); 295 } 296 297 Result->SetSizeLength(PossibleSizeLength); 298 299 Result->Size = SizeFound; 300 301 if (!Result->ValidateSize() || (SizeFound != SizeUnknown && MaxDataSize < Result->Size)) { 302 delete Result; 303 return NULL; 304 } 305 306 // check if the size is not all 1s 307 if (SizeFound == SizeUnknown) { 308 // Size of this element is unknown 309 // only possible for Master elements 310 if (!Result->SetSizeInfinite()) { 311 /// \todo the element is not allowed to be infinite 312 delete Result; 313 return NULL; 314 } 315 } else Result->SetSizeInfinite(false); 316 Result->ElementPosition = aElementPosition; 317 Result->SizePosition = aSizePosition; 318 319 return Result; 320} 321 322 323/*! 324 \todo replace the new RawElement with the appropriate class (when known) 325 \todo skip data for Dummy elements when they are not allowed 326 \todo better check of the size checking for upper elements (using a list of size for each level) 327 \param LowLevel Will be returned with the level of the element found compared to the context given 328*/ 329EbmlElement * EbmlElement::FindNextElement(IOCallback & DataStream, const EbmlSemanticContext & Context, int & UpperLevel, 330 uint64 MaxDataSize, bool AllowDummyElt, unsigned int MaxLowerLevel) 331{ 332 int PossibleID_Length = 0; 333 binary PossibleIdNSize[16]; 334 int PossibleSizeLength; 335 uint64 SizeUnknown; 336 int ReadIndex = 0; // trick for the algo, start index at 0 337 uint32 ReadSize = 0; 338 uint64 SizeFound; 339 int SizeIdx; 340 bool bFound; 341 int UpperLevel_original = UpperLevel; 342 343 do { 344 // read a potential ID 345 do { 346 assert(ReadIndex < 16); 347 // build the ID with the current Read Buffer 348 bFound = false; 349 binary IdBitMask = 1 << 7; 350 for (SizeIdx = 0; SizeIdx < ReadIndex && SizeIdx < 4; SizeIdx++) { 351 if (PossibleIdNSize[0] & (IdBitMask >> SizeIdx)) { 352 // ID found 353 PossibleID_Length = SizeIdx + 1; 354 IdBitMask >>= SizeIdx; 355 bFound = true; 356 break; 357 } 358 } 359 if (bFound) { 360 break; 361 } 362 363 if (ReadIndex >= 4) { 364 // ID not found 365 // shift left the read octets 366 memmove(&PossibleIdNSize[0],&PossibleIdNSize[1], --ReadIndex); 367 } 368 369 if (DataStream.read(&PossibleIdNSize[ReadIndex++], 1) == 0) { 370 return NULL; // no more data ? 371 } 372 ReadSize++; 373 374 } while (!bFound && MaxDataSize > ReadSize); 375 376 SizeIdx = ReadIndex; 377 ReadIndex -= PossibleID_Length; 378 379 // read the data size 380 uint32 _SizeLength; 381 PossibleSizeLength = ReadIndex; 382 while (1) 383 { 384 _SizeLength = PossibleSizeLength; 385 SizeFound = ReadCodedSizeValue(&PossibleIdNSize[PossibleID_Length], _SizeLength, SizeUnknown); 386 if (_SizeLength != 0) { 387 bFound = true; 388 break; 389 } 390 if (PossibleSizeLength >= 8) { 391 bFound = false; 392 break; 393 } 394 ReadSize += DataStream.read(&PossibleIdNSize[SizeIdx++], 1); 395 PossibleSizeLength++; 396 } 397 398 if (bFound) { 399 // find the element in the context and use the correct creator 400 EbmlId PossibleID(PossibleIdNSize, PossibleID_Length); 401 EbmlElement * Result = CreateElementUsingContext(PossibleID, Context, UpperLevel, false, AllowDummyElt, MaxLowerLevel); 402 ///< \todo continue is misplaced 403 if (Result != NULL) { 404 if (AllowDummyElt || !Result->IsDummy()) { 405 Result->SetSizeLength(_SizeLength); 406 407 Result->Size = SizeFound; 408 // UpperLevel values 409 // -1 : global element 410 // 0 : child 411 // 1 : same level 412 // + : further parent 413 if (Result->ValidateSize() && (UpperLevel > 0 || MaxDataSize == 0 || MaxDataSize >= (PossibleID_Length + PossibleSizeLength + SizeFound))) { 414 if (SizeFound == SizeUnknown) { 415 Result->SetSizeInfinite(); 416 } 417 418 Result->SizePosition = DataStream.getFilePointer() - SizeIdx + PossibleID.Length; 419 Result->ElementPosition = Result->SizePosition - PossibleID.Length; 420 // place the file at the beggining of the data 421 DataStream.setFilePointer(Result->SizePosition + _SizeLength); 422 return Result; 423 } 424 } 425 delete Result; 426 } 427 } 428 429 // recover all the data in the buffer minus one byte 430 ReadIndex = SizeIdx - 1; 431 memmove(&PossibleIdNSize[0], &PossibleIdNSize[1], ReadIndex); 432 UpperLevel = UpperLevel_original; 433 } while ( MaxDataSize > DataStream.getFilePointer() - SizeIdx + PossibleID_Length ); 434 435 return NULL; 436} 437 438/*! 439 \todo what happens if we are in a upper element with a known size ? 440*/ 441EbmlElement * EbmlElement::SkipData(EbmlStream & DataStream, const EbmlSemanticContext & Context, EbmlElement * TestReadElt, bool AllowDummyElt) 442{ 443 EbmlElement * Result = NULL; 444 if (bSizeIsFinite) { 445 assert(TestReadElt == NULL); 446 assert(ElementPosition < SizePosition); 447 DataStream.I_O().setFilePointer(SizePosition + CodedSizeLength(Size, SizeLength, bSizeIsFinite) + Size, seek_beginning); 448// DataStream.I_O().setFilePointer(Size, seek_current); 449 } else { 450 ///////////////////////////////////////////////// 451 // read elements until an upper element is found 452 ///////////////////////////////////////////////// 453 bool bEndFound = false; 454 while (!bEndFound && Result == NULL) { 455 // read an element 456 /// \todo 0xFF... and true should be configurable 457// EbmlElement * NewElt; 458 if (TestReadElt == NULL) { 459 int bUpperElement = 0; // trick to call FindNextID correctly 460 Result = DataStream.FindNextElement(Context, bUpperElement, 0xFFFFFFFFL, AllowDummyElt); 461 } else { 462 Result = TestReadElt; 463 } 464 465 if (Result != NULL) { 466 unsigned int EltIndex; 467 // data known in this Master's context 468 for (EltIndex = 0; EltIndex < Context.Size; EltIndex++) { 469 if (EbmlId(*Result) == Context.MyTable[EltIndex].GetCallbacks.GlobalId) { 470 // skip the data with its own context 471 Result = Result->SkipData(DataStream, Context.MyTable[EltIndex].GetCallbacks.Context, NULL); 472 break; // let's go to the next ID 473 } 474 } 475 476 if (EltIndex >= Context.Size) { 477 if (Context.UpTable != NULL) { 478 Result = SkipData(DataStream, *Context.UpTable, Result); 479 } else { 480 assert(Context.GetGlobalContext != NULL); 481 if (Context != Context.GetGlobalContext()) { 482 Result = SkipData(DataStream, Context.GetGlobalContext(), Result); 483 } else { 484 bEndFound = true; 485 } 486 } 487 } 488 } else { 489 bEndFound = true; 490 } 491 } 492 } 493 return Result; 494} 495 496EbmlElement *EbmlElement::CreateElementUsingContext(const EbmlId & aID, const EbmlSemanticContext & Context, 497 int & LowLevel, bool IsGlobalContext, bool bAllowDummy, unsigned int MaxLowerLevel) 498{ 499 unsigned int ContextIndex; 500 EbmlElement *Result = NULL; 501 502 // elements at the current level 503 for (ContextIndex = 0; ContextIndex < Context.Size; ContextIndex++) { 504 if (aID == Context.MyTable[ContextIndex].GetCallbacks.GlobalId) { 505 return &Context.MyTable[ContextIndex].GetCallbacks.Create(); 506 } 507 } 508 509 // global elements 510 assert(Context.GetGlobalContext != NULL); // global should always exist, at least the EBML ones 511 const EbmlSemanticContext & tstContext = Context.GetGlobalContext(); 512 if (tstContext != Context) { 513 LowLevel--; 514 MaxLowerLevel--; 515 // recursive is good, but be carefull... 516 Result = CreateElementUsingContext(aID, tstContext, LowLevel, true, bAllowDummy, MaxLowerLevel); 517 if (Result != NULL) { 518 return Result; 519 } 520 LowLevel++; 521 MaxLowerLevel++; 522 } else { 523 return NULL; 524 } 525 526 // parent elements 527 if (Context.MasterElt != NULL && aID == Context.MasterElt->GlobalId) { 528 LowLevel++; // already one level up (same as context) 529 return &Context.MasterElt->Create(); 530 } 531 532 // check whether it's not part of an upper context 533 if (Context.UpTable != NULL) { 534 LowLevel++; 535 MaxLowerLevel++; 536 return CreateElementUsingContext(aID, *Context.UpTable, LowLevel, IsGlobalContext, bAllowDummy, MaxLowerLevel); 537 } 538 539 if (!IsGlobalContext && bAllowDummy) { 540 LowLevel = 0; 541 Result = new EbmlDummy(aID); 542 } 543 544 return Result; 545} 546 547/*! 548 \todo verify that the size written is the same as the data written 549*/ 550uint32 EbmlElement::Render(IOCallback & output, bool bKeepIntact, bool bKeepPosition, bool bForceRender) 551{ 552 assert(bValueIsSet || (bKeepIntact && DefaultISset())); // an element is been rendered without a value set !!! 553 // it may be a mandatory element without a default value 554 try { 555 if (!bKeepIntact && IsDefaultValue()) { 556 return 0; 557 } 558#if defined(_DEBUG) || defined(DEBUG) 559 uint64 SupposedSize = UpdateSize(bKeepIntact, bForceRender); 560#endif // _DEBUG 561 uint32 result = RenderHead(output, bForceRender, bKeepIntact, bKeepPosition); 562 uint64 WrittenSize = RenderData(output, bForceRender, bKeepIntact); 563#if defined(_DEBUG) || defined(DEBUG) 564 if (SupposedSize != (0-1)) assert(WrittenSize == SupposedSize); 565#endif // DEBUG 566 result += WrittenSize; 567 return result; 568 } catch (std::exception & ex) { 569// const char * What = ex.what(); 570 assert(false); // we should never be here ! 571 return 0; 572 } 573} 574 575/*! 576 \todo store the position of the Size writing for elements with unknown size 577 \todo handle exceptions on errors 578 \todo handle CodeSize bigger than 5 bytes 579*/ 580uint32 EbmlElement::RenderHead(IOCallback & output, bool bForceRender, bool bKeepIntact, bool bKeepPosition) 581{ 582 if (EbmlId(*this).Length <= 0 || EbmlId(*this).Length > 4) 583 return 0; 584 585 UpdateSize(bKeepIntact, bForceRender); 586 587 return MakeRenderHead(output, bKeepPosition); 588} 589 590uint32 EbmlElement::MakeRenderHead(IOCallback & output, bool bKeepPosition) 591{ 592 binary FinalHead[4+8]; // Class D + 64 bits coded size 593 unsigned int FinalHeadSize; 594 595 FinalHeadSize = EbmlId(*this).Length; 596 EbmlId(*this).Fill(FinalHead); 597 598 int CodedSize = CodedSizeLength(Size, SizeLength, bSizeIsFinite); 599 CodedValueLength(Size, CodedSize, &FinalHead[FinalHeadSize]); 600 FinalHeadSize += CodedSize; 601 602 output.writeFully(FinalHead, FinalHeadSize); 603 if (!bKeepPosition) { 604 ElementPosition = output.getFilePointer() - FinalHeadSize; 605 SizePosition = ElementPosition + EbmlId(*this).Length; 606 } 607 608 return FinalHeadSize; 609} 610 611uint64 EbmlElement::ElementSize(bool bKeepIntact) const 612{ 613 if (!bKeepIntact && IsDefaultValue()) 614 return 0; // won't be saved 615 return Size + EbmlId(*this).Length + CodedSizeLength(Size, SizeLength, bSizeIsFinite); 616} 617 618bool EbmlElement::CompareElements(const EbmlElement *A, const EbmlElement *B) 619{ 620 if (EbmlId(*A) == EbmlId(*B)) 621 return *A < *B; 622 else 623 return false; 624} 625 626void EbmlElement::Read(EbmlStream & inDataStream, const EbmlSemanticContext & Context, int & UpperEltFound, EbmlElement * & FoundElt, bool AllowDummyElt, ScopeMode ReadFully) 627{ 628 ReadData(inDataStream.I_O(), ReadFully); 629} 630 631bool EbmlElement::ForceSize(uint64 NewSize) 632{ 633 if (bSizeIsFinite) { 634 return false; 635 } 636 637 int OldSizeLen = CodedSizeLength(Size, SizeLength, bSizeIsFinite); 638 uint64 OldSize = Size; 639 640 Size = NewSize; 641 642 if (CodedSizeLength(Size, SizeLength, bSizeIsFinite) == OldSizeLen) { 643 bSizeIsFinite = true; 644 return true; 645 } 646 Size = OldSize; 647 648 return false; 649} 650 651uint32 EbmlElement::OverwriteHead(IOCallback & output, bool bKeepPosition) 652{ 653 if (ElementPosition == 0) { 654 return 0; // the element has not been written 655 } 656 657 uint64 CurrentPosition = output.getFilePointer(); 658 output.setFilePointer(GetElementPosition()); 659 uint32 Result = MakeRenderHead(output, bKeepPosition); 660 output.setFilePointer(CurrentPosition); 661 return Result; 662} 663 664uint32 EbmlElement::VoidMe(IOCallback & output, bool bKeepIntact) 665{ 666 if (ElementPosition == 0) { 667 return 0; // the element has not been written 668 } 669 670 EbmlVoid Dummy; 671 return Dummy.Overwrite(*this, output, bKeepIntact); 672} 673 674END_LIBEBML_NAMESPACE 675