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