1 // VirtualDub - Video processing and capture application
2 // Copyright (C) 1998-2007 Avery Lee
3 //
4 // This program is free software; you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation; either version 2 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program; if not, write to the Free Software
16 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17
18 #include "stdafx.h"
19 #include <vd2/system/math.h>
20 #include "AVIReadIndex.h"
21
VDAVIReadIndex()22 VDAVIReadIndex::VDAVIReadIndex() {
23 Clear();
24 }
25
~VDAVIReadIndex()26 VDAVIReadIndex::~VDAVIReadIndex() {
27 Clear();
28 }
29
Init(uint32 sampleSize)30 void VDAVIReadIndex::Init(uint32 sampleSize) {
31 mSampleSize = sampleSize;
32 Clear();
33 }
34
IsVBR() const35 bool VDAVIReadIndex::IsVBR() const {
36 return mbVBR;
37 }
38
GetSampleCount() const39 sint64 VDAVIReadIndex::GetSampleCount() const {
40 return mSampleCount;
41 }
42
GetChunkCount() const43 uint32 VDAVIReadIndex::GetChunkCount() const {
44 return mChunkCount;
45 }
46
GetByteCount() const47 sint64 VDAVIReadIndex::GetByteCount() const {
48 return mByteCount;
49 }
50
IsKey(sint64 samplePos) const51 bool VDAVIReadIndex::IsKey(sint64 samplePos) const {
52 if ((uint64)samplePos >= (uint64)mSampleCount)
53 return false;
54
55 uint32 sectorIndex = FindSectorIndexBySample(samplePos);
56 uint32 sampleOffset;
57 uint32 chunkIndex;
58 IndexEntry *ient = FindChunk(samplePos, sectorIndex, sampleOffset, chunkIndex);
59
60 return (sint32)ient->mSizeAndKeyFrameFlag < 0;
61 }
62
PrevKey(sint64 samplePos) const63 sint64 VDAVIReadIndex::PrevKey(sint64 samplePos) const {
64 if (samplePos <= 0)
65 return -1;
66
67 if (samplePos >= mSampleCount)
68 return NearestKey(samplePos);
69
70 uint32 sectorIndex = FindSectorIndexBySample(samplePos);
71 uint32 sampleOffset;
72 uint32 chunkIndex;
73 IndexEntry *ient = FindChunk(samplePos, sectorIndex, sampleOffset, chunkIndex);
74
75 if (chunkIndex == 0)
76 return -1;
77
78 --chunkIndex;
79 for(;;) {
80 ient = &mIndex[chunkIndex >> kBlockSizeBits][chunkIndex & kBlockMask];
81 if ((sint32)ient->mSizeAndKeyFrameFlag < 0) {
82 sectorIndex = FindSectorIndexByChunk(chunkIndex);
83
84 return mSectors[sectorIndex].mChunkOffset + ient->mSampleOffset;
85 }
86
87 if (!chunkIndex)
88 break;
89
90
91 chunkIndex -= ient->mPrevKeyDistance;
92 }
93
94 return -1;
95 }
96
NextKey(sint64 samplePos) const97 sint64 VDAVIReadIndex::NextKey(sint64 samplePos) const {
98 if (samplePos < 0) {
99 if (IsKey(0))
100 return true;
101 samplePos = 0;
102 }
103
104 if (samplePos >= mSampleCount)
105 return -1;
106
107 uint32 sectorIndex = FindSectorIndexBySample(samplePos);
108 uint32 sampleOffset;
109 uint32 chunkIndex;
110 IndexEntry *ient = FindChunk(samplePos, sectorIndex, sampleOffset, chunkIndex);
111
112 while(++chunkIndex < mChunkCount) {
113 ient = &mIndex[chunkIndex >> kBlockSizeBits][chunkIndex & kBlockMask];
114 if ((sint32)ient->mSizeAndKeyFrameFlag < 0) {
115 sectorIndex = FindSectorIndexByChunk(chunkIndex);
116
117 return mSectors[sectorIndex].mChunkOffset + ient->mSampleOffset;
118 }
119 }
120
121 return -1;
122 }
123
NearestKey(sint64 samplePos) const124 sint64 VDAVIReadIndex::NearestKey(sint64 samplePos) const {
125 if (samplePos < 0)
126 return -1;
127
128 if (samplePos >= mSampleCount)
129 samplePos = mSampleCount - 1;
130
131 uint32 sectorIndex = FindSectorIndexBySample(samplePos);
132 uint32 sampleOffset;
133 uint32 chunkIndex;
134 IndexEntry *ient = FindChunk(samplePos, sectorIndex, sampleOffset, chunkIndex);
135
136 for(;;) {
137 if ((sint32)ient->mSizeAndKeyFrameFlag < 0) {
138 sectorIndex = FindSectorIndexByChunk(chunkIndex);
139
140 return mSectors[sectorIndex].mChunkOffset + ient->mSampleOffset;
141 }
142
143 if (chunkIndex <= 0)
144 return -1;
145
146 chunkIndex -= ient->mPrevKeyDistance;
147 ient = &mIndex[chunkIndex >> kBlockSizeBits][chunkIndex & kBlockMask];
148 }
149 }
150
FindSampleRange(VDAVIReadIndexIterator & it,sint64 samplePos,uint32 maxSamples) const151 void VDAVIReadIndex::FindSampleRange(VDAVIReadIndexIterator& it, sint64 samplePos, uint32 maxSamples) const {
152 uint32 sectorIndex = FindSectorIndexBySample(samplePos);
153 uint32 sampleOffset;
154 uint32 chunkIndex;
155 FindChunk(samplePos, sectorIndex, sampleOffset, chunkIndex);
156
157 it.mSectorIndex = sectorIndex;
158 it.mSectorLimit = mSectors[it.mSectorIndex + 1].mChunkOffset;
159 it.mChunkIndex = chunkIndex;
160 it.mChunkOffset = sampleOffset * mSampleSize;
161 }
162
GetFirstSampleRange(VDAVIReadIndexIterator & it) const163 void VDAVIReadIndex::GetFirstSampleRange(VDAVIReadIndexIterator& it) const {
164 it.mSectorIndex = 0;
165 it.mSectorLimit = mSectors[1].mChunkOffset;
166 it.mChunkIndex = 0;
167 it.mChunkOffset = 0;
168 }
169
GetNextSampleRange(VDAVIReadIndexIterator & it,sint64 & chunkPos,uint32 & offset,uint32 & byteSize) const170 bool VDAVIReadIndex::GetNextSampleRange(VDAVIReadIndexIterator& it, sint64& chunkPos, uint32& offset, uint32& byteSize) const {
171 if (it.mSectorIndex >= mSectorCount)
172 return false;
173
174 const SectorEntry& sec = mSectors[it.mSectorIndex];
175 const IndexEntry& ient = mIndex[it.mChunkIndex >> kBlockSizeBits][it.mChunkIndex & kBlockMask];
176
177 chunkPos = sec.mByteOffset + ient.mByteOffset;
178 offset = it.mChunkOffset;
179 byteSize = (ient.mSizeAndKeyFrameFlag & 0x7FFFFFFF) - it.mChunkOffset;
180
181 if (mbVBR && byteSize > mSampleSize) {
182 it.mChunkOffset += mSampleSize;
183 byteSize = mSampleSize;
184 return true;
185 }
186
187 it.mChunkOffset = 0;
188 if (++it.mChunkIndex >= it.mSectorLimit) {
189 ++it.mSectorIndex;
190
191 it.mSectorLimit = mSectors[it.mSectorIndex + 1].mChunkOffset;
192 }
193
194 return true;
195 }
196
Clear()197 void VDAVIReadIndex::Clear() {
198 mbFinalized = false;
199 mbVBR = false;
200 mByteCount = 0;
201 mSampleCount = 0;
202 mChunkCount = 0;
203 mBlockOffset = 0;
204 mPrevKey = 0;
205 mSectors.clear();
206
207 while(!mIndex.empty()) {
208 IndexEntry *ient = mIndex.back();
209 mIndex.pop_back();
210
211 delete[] ient;
212 }
213
214 SectorEntry& sec = mSectors.push_back();
215 sec.mByteOffset = 0;
216 sec.mSampleOffset = 0;
217 sec.mChunkOffset = 0;
218 sec.mbOneSamplePerChunk = true;
219
220 mSectorCount = 1;
221 }
222
AddChunk(sint64 bytePos,uint32 sizeAndKeyFrameFlag)223 void VDAVIReadIndex::AddChunk(sint64 bytePos, uint32 sizeAndKeyFrameFlag) {
224 SectorEntry *sec = &mSectors.back();
225
226 // Note: Some (perhaps broken) AVI files have chunks out of order in the index. In
227 // that case, we must force a new sector.
228
229 if ((uint64)(bytePos - sec->mByteOffset) >= (uint64)0x100000000 || mSampleCount - sec->mChunkOffset >= 0x10000) {
230 sec = &mSectors.push_back();
231 sec->mByteOffset = bytePos;
232 sec->mSampleOffset = mSampleCount;
233 sec->mChunkOffset = mChunkCount;
234 sec->mbOneSamplePerChunk = true;
235 ++mSectorCount;
236 }
237
238 if (mIndex.empty() || mBlockOffset >= kBlockSize) {
239 IndexEntry *newBlock = new IndexEntry[kBlockSize];
240
241 try {
242 mIndex.push_back(newBlock);
243 } catch(...) {
244 delete[] newBlock;
245 throw;
246 }
247
248 mBlockOffset = 0;
249 }
250
251 if ((sint32)sizeAndKeyFrameFlag < 0)
252 mPrevKey = mChunkCount;
253
254 IndexEntry& ient = mIndex.back()[mBlockOffset++];
255
256 ient.mByteOffset = (uint32)bytePos - (uint32)sec->mByteOffset;
257 ient.mSampleOffset = (uint32)mSampleCount - (uint32)sec->mSampleOffset;
258 ient.mSizeAndKeyFrameFlag = sizeAndKeyFrameFlag;
259 ient.mPrevKeyDistance = VDClampToUint16(mChunkCount - mPrevKey);
260 ient.mUnused0 = 0;
261
262 VDASSERT(ient.mByteOffset + sec->mByteOffset == bytePos);
263 VDASSERT(ient.mSampleOffset + sec->mSampleOffset == mSampleCount);
264
265 uint32 chunkSize = sizeAndKeyFrameFlag & 0x7FFFFFFF;
266 if (mSampleSize) {
267 uint32 roundedUpSize = chunkSize + (mSampleSize - 1);
268 uint32 sampleCountInChunk = roundedUpSize / mSampleSize;
269
270 if (chunkSize % mSampleSize)
271 mbVBR = true;
272
273 mSampleCount += sampleCountInChunk;
274
275 if (sampleCountInChunk != 1)
276 sec->mbOneSamplePerChunk = false;
277 } else
278 ++mSampleCount;
279 ++mChunkCount;
280 mByteCount += chunkSize;
281 }
282
Append(const VDAVIReadIndex & src,sint64 bytePosOffset)283 void VDAVIReadIndex::Append(const VDAVIReadIndex& src, sint64 bytePosOffset) {
284 if (mbFinalized) {
285 mSectors.pop_back();
286 mSectors.pop_back();
287 mbFinalized = false;
288 }
289
290 const SectorEntry *sec = &src.mSectors[0];
291 uint32 next = sec[1].mChunkOffset;
292 for(uint32 i=0; i<src.mChunkCount; ++i) {
293 if (i >= next) {
294 ++sec;
295 next = sec[1].mChunkOffset;
296 }
297
298 const IndexEntry& ient = src.mIndex[i >> kBlockSizeBits][i & kBlockMask];
299
300 sint64 bytePos = sec->mByteOffset + bytePosOffset + ient.mByteOffset;
301 AddChunk(bytePos, ient.mSizeAndKeyFrameFlag);
302 }
303
304 Finalize();
305 }
306
Finalize()307 void VDAVIReadIndex::Finalize() {
308 if (mbFinalized)
309 return;
310
311 SectorEntry endSector;
312 endSector.mByteOffset = 0x3FFFFFFFFFFFFFFF;
313 endSector.mChunkOffset = mChunkCount;
314 endSector.mSampleOffset = mSampleCount;
315 mSectors.push_back(endSector);
316 mSectors.push_back(endSector);
317
318 mbFinalized = true;
319 }
320
FindSectorIndexByChunk(uint32 chunk) const321 uint32 VDAVIReadIndex::FindSectorIndexByChunk(uint32 chunk) const {
322 uint32 lo = 0;
323 uint32 hi = mSectorCount - 1;
324
325 while(lo < hi) {
326 uint32 mid = (lo + hi + 1) >> 1;
327 const SectorEntry& midSec = mSectors[mid];
328
329 if (midSec.mChunkOffset <= chunk)
330 lo = mid;
331 else
332 hi = mid - 1;
333 }
334
335 return lo;
336 }
337
FindSectorIndexBySample(sint64 sample) const338 uint32 VDAVIReadIndex::FindSectorIndexBySample(sint64 sample) const {
339 uint32 lo = 0;
340 uint32 hi = mSectorCount - 1;
341
342 while(lo < hi) {
343 uint32 mid = (lo + hi + 1) >> 1;
344 const SectorEntry& midSec = mSectors[mid];
345
346 if (midSec.mSampleOffset <= sample)
347 lo = mid;
348 else
349 hi = mid - 1;
350 }
351
352 return lo;
353 }
354
FindChunk(sint64 sample,uint32 sectorIndex,uint32 & sampleOffsetOut,uint32 & index) const355 VDAVIReadIndex::IndexEntry *VDAVIReadIndex::FindChunk(sint64 sample, uint32 sectorIndex, uint32& sampleOffsetOut, uint32& index) const {
356 const SectorEntry& sec1 = mSectors[sectorIndex];
357 const SectorEntry& sec2 = mSectors[sectorIndex + 1];
358
359 uint32 lo = sec1.mChunkOffset;
360 uint32 hi = sec2.mChunkOffset - 1;
361
362 uint32 sampleOffset = (uint32)sample - (uint32)sec1.mSampleOffset;
363
364 if (sec1.mbOneSamplePerChunk) {
365 index = sec1.mChunkOffset + sampleOffset;
366 sampleOffsetOut = 0;
367 return &mIndex[index >> kBlockSizeBits][index & kBlockMask];
368 }
369
370 IndexEntry *ient = nullptr;
371 uint32 mid;
372 while(lo < hi) {
373 mid = (lo + hi + 1) >> 1;
374 ient = &mIndex[mid >> kBlockSizeBits][mid & kBlockMask];
375
376 if (ient->mSampleOffset <= sampleOffset)
377 lo = mid;
378 else
379 hi = mid - 1;
380 }
381
382 ient = &mIndex[lo >> kBlockSizeBits][lo & kBlockMask];
383 sampleOffsetOut = sampleOffset - ient->mSampleOffset;
384 index = lo;
385 return ient;
386 }
387