RECOVER EXT3 - Bootstraping the miniproject

Hi,
And now its time for our miniproject. We have decided to have the mini-project with the team , me,midhun,and vijin and vyshakh as usual. As for ever it was really difficult to make decision over what should be the project. Somehow we got the idea of a file recovery tool, and we saw that there is not so much such tools for the ext3 filesystem. Thus another story begins here 'The mini project days'.

We googled for the available documentations over the file recovery in ext3. There were not so docs in bulk, but the available once where capable of keeping the idea alive. We went through the documents of 'ext3grep' and some other saying 'file system forensic' neither of the documents said its easy to recover the lost files but they did say there is chances that the files can be recovered using the details in journal.

As we gone through a number of different documents, almost al of them were discribing the recovery method in some what similar way. All of them were using the tools TSK, foremost etc. Although there is no point in discribing the procedure in those articles here, they do come in the scope of the post. Lets have a higher level look over the structure of the inode of a file and how these articles recover the lost data.
The inode in the ext3 file-system
An image of the disk is created ( from where the file was deleted..).
The inode corresponding to the deleted file has been found.(The tool debugfs can be used for this)
The block group of the inode is obtained from 'imap' in debugfs.
The journal of the file is searched to get the entries for the particular inode in the blockgroup.
The journalled inode data is fetched and if it is of some size near our deleted file, the file is recovered using the tools like 'foremost'.

Here the major threat we faced is that using these tools recovery of a file which has its data present in the single, double and triple indirect pointers is not so easy. There is another problem that it can recover the files with extensions which are defined in the foremost only. Enhancing the foremost for the unavailable extensions is also didn't sound so good to us. As of now we had been on our way to find some simple but robust method that can better recover the file irrespective of the file size.

Then we thought if there was an option to undo the permanent deletion till its not over written then it would have been fine. That means if we are able to make the OS believe that file had not yet been deleted then it would have been easy to tackle this undeletion. Yeah here comes our idea behind the miniproject wich is robust and sound. Re-establishing the previous contents of the inode to itself will do the undeletion till the data is not overwritten. There is tools which will help to get the journal details to recover the datas in an inode at a previous time also to edit the inode, and these tools can be used to start the project and later these can be replaced with our own dedicated code.
And thus here is a turning point.......

EMBEDED TETRIS REVISITED

Even the tetris failed to be exhibited due to the low brightness of the LED's, it was a great experience.It was a week ahead of our department program Insignia, and my class mates and me were searching every where for an idea of project. The lack of time kept us away from start projects from scratch. The team behind the റെതൃസ് decided to gave it a new birth, but this time there was another newbie team ready to take the challenge. Jaslina, Merlin and Abitha were ready to re-implement the idea with a new code and slight change in the circuit ( the changes ie the structure of the new project is described below) .

This time we decided to go with an etched circuit. Regarding the code, Abitha, Jaslina and Merlin could re-write the complete code where the job for me and Vyshakh was just helping them. After the effort of a few days the three colleagues of us could write a new code which was robust than the previous one, where the core ideas remained the same.

The soldering left in the etched board was done by the three itself..( another piece of perfect work from another newbies..)

Although it was for the first time these ത്രീ working with embedded programming there was nothing left in the code to be edited after the code was etched. The code ran in the first burning itself. It was really the greatest experience to see the tetrades falling one by one and changing there position and rotating with the keys...

The circuit:

• The tetris board is the same led dot matrix in which the negative legs of the 14 leds in each row are shorted positive legs of the 28 leds in each column are shorted.
  
• The 14 column are controlled directly from the micro controller through ports B and C.
  
• The 28 rows are controlled by decoded outputs through portA ie one row can be selected at a time.
  
• The score is shown in 7segment display whose ic is controlled by 4 inputs ( 3 from port A and 1 from port C)
  
• A 8 Mhz crystal is connected to the micro controller because the internal frequency of the mc which 4 Mhz will not be sufficient for the back ground programm of tetris to work.

Background program:

• Data structure used
  
  • The teris board is a single dimension integer array of length 28.
    
  • The shapes(tetrades) are single dimension array of integers terminated by negative values. Binary equivalent of the positive numbers in the shape array corresponds to the shape and the terminating negative number denote the maximum breadth of the shape.
    
  • Another variable for shifting the shape is used in the code which is just an integer whose default value is 6 and a left key press will increase the value of the variable and right key press will decrease it by 1.
    
  
  
• Operation
  
  • Check for fall- to check whether a shape can fall a row down we have to look whether the 1 of the shape(tetrade) will overlap with any one in the board if all rows of the shape is pushed one row downwards, and if there is no such overlapping the shape can fall a row down.
    This checking is down based on the nature of binary numbers that a+b(addition) and a(+)b (bitwise X-oring ) will be the same if no two 1s are X-ored together. That means if the result of addition and X-or are the same the tetrade can fall.
    
  
  
• Algorithm for The Back ground Program
  
  1. The back-ground program will randomly select shapes from the array of shapes.
     
  2. The board is displayed such that ith row and value in ith row are selcted for all i<28>
  3. The game is over is the shape left shifted withe a value (say l) cannot be inserted to the board.
     
  4. The keys are read and the value of 'l' is updated for a left or right key and the shape is changed to the next change in the sequence of the present one, for a key press for rotation. nb: the updation of shape or l will take place only if the shape can exist in the board with the updated index of shape or vale of 'l'.
     
  5. The shape is made to fall a row down if it can fall down. and the algorithm is repeated from step2. And if the shape cannot fall down the Algorithm is repeated from step1.
     
  
  

Here is the micro controller code

THE EMBEDDED TETRIS

Making the 'embeded tetris' was the greatest ever experience of mine. The story of the emebeded tetris is a little bit old by now, and was scratched by Sailesh, my room mate after the running display. As the summer vacation has just started we the team of five ( Me, Vijin, Vyshakh, Tony and Sailesh ) thought to have a walk through the idea of Sailesh.

The extract of the discussion over the components and the abstract of the project get concluded to use an ATmega16 microcontroller to run the background code for the tetriss and to control the 14*28 led board along with the score and 4*4 leds showing the next shape. The most interesting factor was that we decided to go with our circuit drawn nowhere other than the idea we ha

ve in our minds.

Actually at first t

h

e 'walk' did really took its litera
l meaning. we a

h

d decided to go along with a 14*28 led board for tetris. And t

he ernakulam trip to buy the LED's and other components stole a whole long day from our life in wandering through the city of ernakulam to find the apt shop to buy

the components. But later it was nice to see the day crypted in the unforgattable letters and the the silly mistakes, painted in colours of comedy.

Though we were just newbies in soldering circuit of the tetriss was completed in a jiffy, thanks to the great effort from our team. What made us still proud about the soldering was nothing other than we could make the circuit without much ovelapping of wires without the help of a circuit. We had the circuit diagram only in our idea and it never seemed difficult to solder the four pieces of p

cbs at the same time by 4 of us and joining them without much overlapping.

The 400+ soldered Led's just looked professional.

The circuit was designed to control the 14 coloumns and 28 rows through decoders, ie one each from the coloumns and rows can be selected at a time. The 16 led's for showing next was also designed to control through decoders. a complete port of the micro controller was left dedicated to sho

w the score. The 28 rows controllers also used a port by its own. The next and the coloumn controlls were multiplexed to one port. And the fourth port was configured as input to connect the keyboard.

But the tetris was not over with the circuit alone.

It is still interesting to remember the discussion in our team which started with a word tetris and ended up in making a frame

work of the tetris' background program, perhaps the most robust frame for such a game. Decissions over the data structure for the tetris board and the shapes were great milestones in the discussion. When it was first decided to have the data structure of the tetris board, as a single dimension stack, and the shapes, to be single dimension array of integers terminated with -ve numbers indicating the size of the shape, we were still to believe that they are the most efficient data structures for tetriss. So was the case for the decision over the operation behind the movement of the shape in the board, which was the comparison between X-OR ing and addition.

The story was not yet over...

As an exhibition in our college was at the door Tetriss was needed to be finished in a fly. But all others other than Tony and Vyshakh got engaged in some other works in the late hours. Then it was the real challenge as the circuit was never drawn any where nor it was simulated before. The case for the code was not much different as the code was going to be tested for the first time. It took a whole long day to solve the little mistakes by the newbies both in the code and circuit. Atlast the tetrads began to fall in the tetriss and they moved with the keys, but the ultimate victory was not anywhere near in the sight, the light from the led's was too low that the we couldn't exhibit the tetriss. Again the mistakes from the newbies.. the wires and interconnections was not so efficient to switch the voltages at the frequency of the microcontroller....

But quest to see the circuit designed by us working gave the tetriss a new birth...........