// http://www.warrenstutt.com/AAL77FDRDecompressor/Source/AAL77FDRDecompressor.zip
// AAL77FDRDecompressor/AAL77FDRDecompressor/Program.cs
1: using System;
2: using System.Collections.Generic;
3: using System.Linq;
4: using System.Text;
5: using System.IO;
6:
7: namespace AAL77FDRDecompressor
8: {
9: //Version 1.0
10:
11: //This class allows the input file to be read in units of 128 byte pages.
12: public class PageFileStream
13: {
14: private const int blockLength = 0x20000;
15:
16: private FileStream inputFile = null;
17: private int inputFileOffset = 0;
18: private int inputFileStart = 0;
19: private int inputFileLength = 0;
20: private int inputFilePos = 0;
21:
22: public PageFileStream(string fileName)
23: {
24: inputFile = new FileStream(fileName, FileMode.Open, FileAccess.Read);
25: int fl = (int)inputFile.Length;
26: bool finished = false;
27: //Search through each pair of 64KB blocks for the earliest recorded data
28: //and find out how long the data is not including the text header at the
29: //beginning of the file.
30: for (int fp = fl - blockLength; (fp >= 0) && (!finished); fp -= blockLength)
31: {
32: inputFile.Seek(fp, SeekOrigin.Begin);
33: byte[] headerBytes = new byte[2];
34: inputFile.Read(headerBytes, 0, headerBytes.Length);
35: int headerWord = (headerBytes[1] << 8) | headerBytes[0];
36: switch (headerWord)
37: {
38: case 0xFE6B:
39: //This is a pair of 64KB blocks containing valid data.
40: inputFileOffset = fp;
41: break;
42: case 0xFFFF:
43: //This is the pair of blank blocks which is left erased and ready to
44: //be used when the current pair of blocks is full so the earliest
45: //recorded data is the next pair of 64KB blocks.
46: inputFileOffset = fp;
47: inputFileStart = fp + blockLength;
48: break;
49: default:
50: //This is invalid data so we must be looking through the text header
51: //at the beginning of the file.
52: finished = true;
53: break;
54: }
55: }
56: if (inputFileStart >= fl)
57: inputFileStart = inputFileOffset;
58: //Calculate the start point and length of the data in units of 128 byte pages.
59: inputFileStart = (inputFileStart - inputFileOffset) >> 7;
60: inputFileLength = (fl - inputFileOffset) >> 7;
61: Seek(0);
62: }
63:
64: public int Length
65: {
66: get
67: {
68: return inputFileLength - (blockLength >> 7);
69: }
70: }
71:
72: public int BytePos(int fp)
73: {
74: //Calculate the byte file offset of a file offset measured in units of 128 byte
75: //pages. Offset 0 is the earliest recorded data. The recorded data wraps around
76: //to the beginning of the file as in a standard ring buffer.
77: int pagePos = fp + inputFileStart;
78: if (pagePos >= inputFileLength)
79: pagePos -= inputFileLength;
80: return ((pagePos << 7) + inputFileOffset);
81: }
82:
83: public void Seek(int fp)
84: {
85: //Seek in to the file in units of 128 byte pages.
86: inputFile.Seek(BytePos(fp), SeekOrigin.Begin);
87: inputFilePos = fp;
88: }
89:
90: public byte[] ReadPage()
91: {
92: //Read a single 128 byte page.
93: byte[] page = new byte[128];
94: inputFile.Read(page, 0, page.Length);
95: if ((++inputFilePos + inputFileStart) == inputFileLength)
96: Seek(inputFilePos);
97: return page;
98: }
99:
100: public void Close()
101: {
102: inputFile.Close();
103: }
104: }
105:
106: abstract class HuffmanCodeNode
107: {
108: public bool IsLeaf
109: {
110: get
111: {
112: return this is HuffmanCodeLeafNode;
113: }
114: }
115: }
116:
117: //This class is for interior (non leaf) nodes of the Huffman tree.
118: class HuffmanCodeInteriorNode : HuffmanCodeNode
119: {
120: private HuffmanCodeNode[] child = null;
121:
122: public HuffmanCodeInteriorNode()
123: {
124: child = new HuffmanCodeNode[2];
125: for (int i = 0; i < child.Length; i++)
126: child[i] = null;
127: }
128:
129: public HuffmanCodeNode GetChild(int i)
130: {
131: return child[i];
132: }
133:
134: //Add Huffman codes and values (referred to as differences here) to the Huffman tree.
135: //The Huffman codes have the form pppppxxxxx in binary.
136: //The p bits are from prefix which is a string representation of a binary number.
137: //The x bits are related to the differences. There are a total of numBits x bits.
138: //A non-negative differences is considered as a 12 bit signed integer, the first x bit
139: // is the sign of the integer. The other x bits are a binary representation of
140: // the absolute value of the integer.
141: //A difference of -1 represents a loss of synchronisation and the end of a segment of
142: // compressed data.
143: public void AddHuffmanCodesForPrefix(string prefix, int startDifference, int numBits)
144: {
145: //Add the prefix to the Huffman tree.
146: HuffmanCodeNode huffmanCodeNode = this;
147: for (int i = 0; i < prefix.Length; i++)
148: {
149: int bit = int.Parse(prefix[i].ToString());
150: HuffmanCodeNode nextHuffmanCodeNode = ((HuffmanCodeInteriorNode)huffmanCodeNode).child[bit];
151: if (nextHuffmanCodeNode == null)
152: {
153: if ((numBits == 0) && (i == prefix.Length - 1))
154: {
155: ((HuffmanCodeInteriorNode)huffmanCodeNode).child[bit] = new HuffmanCodeLeafNode(startDifference);
156: return;
157: }
158: else
159: {
160: nextHuffmanCodeNode = new HuffmanCodeInteriorNode();
161: ((HuffmanCodeInteriorNode)huffmanCodeNode).child[bit] = nextHuffmanCodeNode;
162: }
163: }
164: huffmanCodeNode = nextHuffmanCodeNode;
165: }
166: //Add each difference to the Huffman tree, starting with startDifference.
167: Stack<HuffmanCodeNode> huffmanCodeNodeStack = new Stack<HuffmanCodeNode>();
168: int difference = startDifference;
169: while (true)
170: {
171: bool createdHuffmanCodeNode = false;
172: for (int i = 0; i < ((HuffmanCodeInteriorNode)huffmanCodeNode).child.Length; i++)
173: {
174: HuffmanCodeNode nextHuffmanCodeNode = ((HuffmanCodeInteriorNode)huffmanCodeNode).child[i];
175: if (nextHuffmanCodeNode == null)
176: {
177: if (huffmanCodeNodeStack.Count < numBits - 1)
178: {
179: nextHuffmanCodeNode = new HuffmanCodeInteriorNode();
180: ((HuffmanCodeInteriorNode)huffmanCodeNode).child[i] = nextHuffmanCodeNode;
181: huffmanCodeNodeStack.Push(huffmanCodeNode);
182: huffmanCodeNode = nextHuffmanCodeNode;
183: }
184: else
185: {
186: ((HuffmanCodeInteriorNode)huffmanCodeNode).child[i] = new HuffmanCodeLeafNode(difference);
187: if (difference < 0x800)
188: difference++;
189: else
190: difference--;
191: }
192: createdHuffmanCodeNode = true;
193: break;
194: }
195: }
196: if (!createdHuffmanCodeNode)
197: {
198: if (huffmanCodeNodeStack.Count < 1)
199: break;
200: huffmanCodeNode = huffmanCodeNodeStack.Pop();
201: if (huffmanCodeNodeStack.Count < 1)
202: difference = 0x1000 - startDifference;
203: }
204: }
205: }
206: }
207:
208: class HuffmanCodeLeafNode : HuffmanCodeNode
209: {
210: private int difference = 0;
211:
212: public HuffmanCodeLeafNode(int aDifference)
213: {
214: difference = aDifference;
215: }
216:
217: public int Difference
218: {
219: get
220: {
221: return difference;
222: }
223: }
224: }
225:
226:
227: //The following class holds the current state of one of the two independent flight data streams.
228:
229: //Information about the format in which the FDR records the data can be found in the post
230: //at http://forums.randi.org/showpost.php?p=2022420&postcount=85 and in figure 4.2-2 of
231: //the document http://www.asc.gov.tw/author_files/ASC-TRT-99-007.pdf
232:
233: //Flight Data Stream 0 consists of the first, third, fifth and so on blocks of 512 pages from
234: //the PageFileStream.
235:
236: //Flight Data Stream 1 consists of the second, fourth, sixth and so on blocks of 512 pages from
237: //the PageFileStream.
238:
239: //The first 2 pages from each block of 512 pages are header pages that also contain Bad Page
240: //Maps. This program ignores these pages.
241:
242: //The words within the other pages in the figure are 16 bit words stored Least Significant Byte
243: //first and the Hamming code & page parity occupy the last 11 bits of each page. Within each
244: //16 bit word, the most significant bit is the first bit in the bit stream. Some pages are
245: //blank consisting entirely of 0xFFFF words and need to be skipped. The Hamming code and page
246: //parity are ignored by this program. My AAL77 Hamming code and page parity checker program
247: //does read them however.
248:
249: //Data is recorded by the FDR in frames separated by the 16 bit frame marker word 0xFEFE. A
250: //frame consists of 4 subframes of 256 12 bit words. A subframe consists of 1 second of data.
251: //The FDR does not record the first 12 bit word of each subframe since they are sync words
252: //and are always the same. Therefore a complete frame is stored as 1020 * 12 bit words. The
253: //subframes are numbered 1 to 4 and appear in that order in each frame.
254:
255: //The frames are recorded in a compressed form using Huffman coding. At the beginning of each
256: //section of compressed data within a flight data stream and periodically every 75 frames, a
257: //baseline frame is recorded that consists of the Huffman codes of each of the 1020 * 12 bit
258: //words. Each baseline frame is preceded with the bits 1000 and a 16 bit frame counter.
259:
260: //The other frames are recorded by calculating the difference between each of the 1020 * 12 bit
261: //words in this frame and the one before it in this flight data stream. The Huffman codes of
262: //these differences are recorded for those frames. Each of these frames are preceded with a
263: // 0 bit.
264:
265: //Except for the baseline frame at the beginning of each section of compressed data in a flight
266: //data stream, the baseline frames are additional copies of the current frame, i.e. the
267: //baseline frames need to not appear in the decoded output, to avoid 2 copies of the same frame
268: //of data appearing. This program does not output the first baseline frame at the beginning of
269: //each section of compressed data, so that adds up to 8 seconds of data at the beginning of
270: //each section of compressed data that is not decoded.
271:
272: //Frames are alternately stored in each of the flight data streams so one flight data stream
273: //will consist of the first, third, fifth and so on frames of data and the other flight data
274: //stream will have the second, fourth, sixth and so on frames of data. A frame counter is
275: //recorded along with each baseline frame that makes it possible to determine which flight data
276: //stream contains the first frame of data.
277:
278: //A special Huffman code is used to mark the loss of synchronisation and the subsequent end of
279: //the section of compressed data. This can occur at any point within the frame which is why the
280: //last frame of data within a section of compressed data is less than 1020 * 12 bit words.
281:
282: //In between the sections of compressed data, up to 4 subframes of uncompressed data is
283: //generated in the file each time the FDR is started up which I believe happens when the
284: //engines are started. My AAL77 FDR partial decoder program decodes the uncompressed data.
285:
286: class FlightDataStream
287: {
288: enum FrameStates { StartState, GetFrameType, GetCounter, DecompressFrame, WaitUntilEnd };
289:
290: private int[] frame = new int[1020];
291: private byte[] page = null;
292: private HuffmanCodeNode huffmanCodeTree = null;
293: private FrameStates frameState = FrameStates.StartState;
294: private int numFlightDataStreams = 0;
295: private int subFrameNumber = 0;
296: private int superFrameNumber = 0;
297: private int counter = -1;
298: private int lastFramePos = 0;
299: private int bitPos = 0;
300: private int pageNum = 0;
301: private int filePos = 0;
302: private int lastWordPos = -1;
303: private int w = 0;
304: private bool syncLost = false;
305: private bool endOfData = false;
306: private bool baseLineFrame = false;
307: private bool badFrame = false;
308:
309: public FlightDataStream(HuffmanCodeNode aHuffmanCodeTree, int flightDataStreamNumber, int aNumFlightDataStreams)
310: {
311: huffmanCodeTree = aHuffmanCodeTree;
312: numFlightDataStreams = aNumFlightDataStreams;
313: for (int i = 0; i < frame.Length; i++)
314: frame[i] = 0;
315: pageNum = (flightDataStreamNumber << 9) + 2;
316: }
317:
318: public int Counter
319: {
320: get
321: {
322: return counter;
323: }
324: }
325:
326: public bool EndOfProcessedFrames
327: {
328: get
329: {
330: return (endOfData && (frameState == FrameStates.StartState));
331: }
332: }
333:
334: public void ReadFrame()
335: {
336: HuffmanCodeNode huffmanCodeNode = huffmanCodeTree;
337: int framePos = 0;
338: int lastFramePosWith0Bit = -1;
339: int frameType = 0;
340: int frameTypeBits = 0;
341: int counterBits = 0;
342: syncLost = false;
343: while (!endOfData)
344: {
345: //The last 11 bits of the 128 byte (1024 bit) page are the Hamming Code and page
346: //parity which this code skips.
347: if ((bitPos >= 1013) || (page == null))
348: {
349: bitPos = 0;
350: bool emptyPage = true;
351: //Skip empty pages (pages where all bits are 1)
352: while (emptyPage)
353: {
354: Program.inputFile.Seek(pageNum);
355: page = Program.inputFile.ReadPage();
356: pageNum++;
357: if ((pageNum & 0x1FF) == 0)
358: //We are at the end of a block of pages so go the first data page
359: //within the next block of pages in this flight data stream.
360: pageNum += 0x202;
361: for (int bp = 0; bp < page.Length; bp++)
362: if (page[bp] != 0xFF)
363: {
364: emptyPage = false;
365: break;
366: }
367: }
368: }
369: if (pageNum >= Program.inputFile.Length)
370: {
371: endOfData = true;
372: filePos = Program.inputFile.BytePos(pageNum);
373: break;
374: }
375: int wordPos = bitPos >> 4;
376: if (wordPos != lastWordPos)
377: {
378: w = (page[(wordPos << 1) | 1] << 8) | page[(wordPos << 1)];
379: lastWordPos = wordPos;
380: if ((w == 0xFEFE) && (wordPos != 63) && (frameState == FrameStates.WaitUntilEnd))
381: {
382: bitPos += 0x10;
383: filePos = Program.inputFile.BytePos(pageNum - 1) + ((bitPos >> 3) & 0x7E);
384: //We have now finished reading this frame
385: break;
386: }
387: }
388: int bit = (w >> (0xF - (bitPos++ & 0xF))) & 1;
389: switch (frameState)
390: {
391: case FrameStates.StartState:
392: huffmanCodeNode = huffmanCodeTree;
393: framePos = 0;
394: lastFramePosWith0Bit = -1;
395: badFrame = false;
396: if (baseLineFrame = (bit == 1))
397: {
398: //This could be a baseline frame, read the frame type.
399: frameType = 0;
400: frameTypeBits = 0;
401: frameState = FrameStates.GetFrameType;
402: }
403: else
404: {
405: //Start decoding this non baseline frame.
406: counter += numFlightDataStreams;
407: frameState = FrameStates.DecompressFrame;
408: }
409: break;
410: case FrameStates.GetFrameType:
411: frameType = (frameType << 1) | bit;
412: if (++frameTypeBits >= 3)
413: if (frameType == 0)
414: {
415: //Read the counter value for this baseline frame.
416: counter = 0;
417: counterBits = 0;
418: frameState = FrameStates.GetCounter;
419: }
420: else
421: {
422: //This data is not a compressed frame.
423: badFrame = true;
424: frameState = FrameStates.WaitUntilEnd;
425: }
426: break;
427: case FrameStates.GetCounter:
428: counter = (counter << 1) | bit;
429: if (++counterBits >= 16)
430: //Start decoding this baseline frame.
431: frameState = FrameStates.DecompressFrame;
432: break;
433: case FrameStates.DecompressFrame:
434: if (bit == 0)
435: lastFramePosWith0Bit = framePos;
436: //Follow the Huffman code tree.
437: huffmanCodeNode = ((HuffmanCodeInteriorNode)huffmanCodeNode).GetChild(bit);
438: if (huffmanCodeNode.IsLeaf)
439: {
440: //We now have read a complete Huffman code. Get the difference.
441: int difference = ((HuffmanCodeLeafNode)huffmanCodeNode).Difference;
442: if (difference < 0)
443: {
444: //The Huffman code just read was the special loss of
445: //synchronisation code. Wait for the frame marker word.
446: syncLost = true;
447: badFrame = true;
448: frameState = FrameStates.WaitUntilEnd;
449: }
450: else
451: {
452: //Add the difference to the 12 bit word for a non-baseline frame,
453: //or overwrite the 12 bit word with the difference for a baseline
454: //frame.
455: frame[framePos] = ((baseLineFrame ? 0 : frame[framePos]) + difference) & 0xFFF;
456: //Start reading the next Huffman code.
457: huffmanCodeNode = huffmanCodeTree;
458: if (++framePos >= frame.Length)
459: //We now have a full frame, wait for the frame marker word.
460: frameState = FrameStates.WaitUntilEnd;
461: }
462: }
463: break;
464: case FrameStates.WaitUntilEnd:
465: //The rest of the bits remaining before the frame marker word should all be 1
466: if (bit != 1)
467: badFrame = true;
468: break;
469: }
470: }
471: lastFramePos = endOfData ? lastFramePosWith0Bit + 1 : framePos;
472: if (lastFramePos > 764)
473: superFrameNumber = (frame[764] >> 8) + 1;
474: else
475: if (superFrameNumber >= 0)
476: superFrameNumber = ((superFrameNumber + numFlightDataStreams - 1) % 16) + 1;
477: }
478:
479: public void ReadGoodBaseLineFrame()
480: {
481: superFrameNumber = -1;
482: //Keep reading frames until we get a good baseline frame.
483: while (((!baseLineFrame) || badFrame) && (!endOfData))
484: {
485: frameState = FrameStates.StartState;
486: ReadFrame();
487: }
488: }
489:
490: string BinaryStringOfWord(int word)
491: {
492: string result = "";
493: for (int i = 11; i >= 0; i--)
494: result += ((word >> i) & 1).ToString();
495: return result;
496: }
497:
498: //This method writes the frame contents to the output file.
499: public bool RecordFrame()
500: {
501: int[] syncWords = { 583, 1464, 2631, 3512 };
502:
503: //Only record non baseline frames that have some data in them.
504: if ((!baseLineFrame) && (lastFramePos > 0))
505: {
506: int framePos = 0;
507: //Cycle through each subframe within the frame.
508: for (subFrameNumber = 1; subFrameNumber <= 4; subFrameNumber++)
509: {
510: if (lastFramePos <= framePos)
511: break;
512: string line = BinaryStringOfWord(syncWords[subFrameNumber - 1]);
513: for (int wordNum = 2; wordNum <= 256; wordNum++)
514: if (lastFramePos > framePos)
515: line += " " + BinaryStringOfWord(frame[framePos++]);
516: else
517: break;
518: Program.outputFile.WriteLine(line);
519: }
520: if (syncLost)
521: Program.outputFile.WriteLine("Sync Lost");
522: }
523: frameState = FrameStates.StartState;
524: return syncLost;
525: }
526: }
527:
528: class GenerateOutput
529: {
530: public bool Start()
531: {
532: //Construct the Huffman code tree.
533: HuffmanCodeInteriorNode huffmanCodeTree = new HuffmanCodeInteriorNode();
534: huffmanCodeTree.AddHuffmanCodesForPrefix("0", 0, 0);
535: huffmanCodeTree.AddHuffmanCodesForPrefix("10", 1, 2);
536: huffmanCodeTree.AddHuffmanCodesForPrefix("110", 3, 3);
537: huffmanCodeTree.AddHuffmanCodesForPrefix("1110", 7, 4);
538: huffmanCodeTree.AddHuffmanCodesForPrefix("111100", 15, 5);
539: huffmanCodeTree.AddHuffmanCodesForPrefix("1111100", 31, 6);
540: huffmanCodeTree.AddHuffmanCodesForPrefix("1111010", 63, 7);
541: huffmanCodeTree.AddHuffmanCodesForPrefix("111111", 127, 8);
542: huffmanCodeTree.AddHuffmanCodesForPrefix("1111101", 255, 9);
543: huffmanCodeTree.AddHuffmanCodesForPrefix("11110110", 511, 10);
544: huffmanCodeTree.AddHuffmanCodesForPrefix("111101110", 1023, 11);
545: huffmanCodeTree.AddHuffmanCodesForPrefix("1111011110", 2047, 2);
546: huffmanCodeTree.AddHuffmanCodesForPrefix("1111011111", -1, 0); //This is the special Huffman code that marks loss of synchronisation.
547: FlightDataStream[] flightDataStream = new FlightDataStream[2];
548: for (int flightDataStreamNumber = 0; flightDataStreamNumber < flightDataStream.Length; flightDataStreamNumber++)
549: flightDataStream[flightDataStreamNumber] = new FlightDataStream(huffmanCodeTree, flightDataStreamNumber, flightDataStream.Length);
550: bool syncLost = true;
551: while (true)
552: {
553: if (syncLost)
554: {
555: //We have reached the end of a section of compressed data. Find the next good
556: //baseline frame for both flight data streams.
557: for (int flightDataStreamNumber = 0; flightDataStreamNumber < flightDataStream.Length; flightDataStreamNumber++)
558: flightDataStream[flightDataStreamNumber].ReadGoodBaseLineFrame();
559: syncLost = false;
560: }
561: //Determine which flight data stream has the current frame with the lowest counter
562: //value. This will be the frame to be recorded to the output next.
563: int firstFlightDataStreamNumber = -1;
564: int firstCounter = -1;
565: for (int flightDataStreamNumber = 0; flightDataStreamNumber < flightDataStream.Length; flightDataStreamNumber++)
566: if (!flightDataStream[flightDataStreamNumber].EndOfProcessedFrames)
567: {
568: int counter = flightDataStream[flightDataStreamNumber].Counter;
569: if ((firstCounter < 0) || (((counter - firstCounter) & 0x8000) != 0))
570: {
571: firstFlightDataStreamNumber = flightDataStreamNumber;
572: firstCounter = counter;
573: }
574: }
575: if (firstFlightDataStreamNumber < 0)
576: //No data to be recorded was found so the output is finished.
577: break;
578: if (flightDataStream[firstFlightDataStreamNumber].RecordFrame())
579: //The loss of synchronisation code was found within the frame just recorded to
580: //the output so we are at the end of this section of compressed data.
581: syncLost = true;
582: flightDataStream[firstFlightDataStreamNumber].ReadFrame();
583: }
584: return (true);
585: }
586: }
587:
588: class Program
589: {
590: static public PageFileStream inputFile = null;
591: static public StreamWriter outputFile = null;
592:
593: static void Main(string[] args)
594: {
595: inputFile = new PageFileStream(@"C:\Documents and Settings\Admin\My Documents\Pilots For 911 Truth\090324_0813\AA77 FDR\American 77.fdr");
596: outputFile = new StreamWriter(@"C:\Documents and Settings\Admin\My Documents\Pilots For 911 Truth\AAL77 Decompressed.txt");
597: GenerateOutput generateOutput = new GenerateOutput();
598: generateOutput.Start();
599: outputFile.Close();
600: inputFile.Close();
601: }
602: }
603: }