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...........

RUNNING DISPLAY WITH 224 LEDs- A review..

RUNNING DISPLAY

Little projects with LEDs are always interesting. The most interesting thing about these is that the core idea behind all of these is the same, whether the work be a chaser or display and it’s the very principle which was explored by the inventors of movies. That means when we are about to do something like this chasers or any kind of displays what we have to do is mere exploring of the simple principle behind the chaser properly till it can give us a frame sufficient enough to have our work done. And the principle is nothing but switching a set of LEDs one by one ON in a sequence and of course in a timely manner. As an example lets consider the parallel port of a pc which has 8 output pins in a port (port no: 0x378) which can be controlled independently now lets assume these to be 8 switches which we can control and each is being in series with an LED. If we can operate these switches one by one faster enough, we can have a chaser with 8 LEDs controlled by our hand, which can be very easily done in a computer, having speed in range of GHz.

When it comes to control more and more objects (say LEDs) the easiest way for someone who is fresh to the digital electronics field is using decoders which enables us to control up to 2^n objects with n inputs. But the decoder is having a great barrier for us on our way from experiments to experiments that the decoder are capable of selecting only one output at a time. It is sure that the way towards success may not be so easy ever, it will be having walls of different heights, but the mind which is thirsty of success will never stop. On this behavior of the decoder we have the great speed of a computer or micro-controller which can mask the inability of selecting multiple outputs at a time. That is if we want to select some n outputs simultaneously through a decoder (or to light up some n number of LEDs at a time) let us select these one by one in short span of time in between (say in micro seconds, its possible to be even faster ) and continue selecting them one by one for some time. In this case the viewers even the very ones who know what is being done actually can not measure or see the time gap between these outputs (the human eye can see two things separately if there is a time gap of at least 1/16^th of a second which can not be even compared with the speed of computers ). This is the very idea (principle) which is being exploited in our running display. Let us see in detail how the idea is being explored at some points of our journey towards the success of the running display.

The first thing to be done for the work of display was to decide the dimensions of the LED matrix that can represent all the letters numbers and special characters in the ASCII character set. An array of 7*5 came sufficient for this case. It’s not convenient to have each word and sentence get coded for our display or in other words we should have a general table which is having the display representations for each and every character, which we can define by our own. That is here we are going to define a special behavior for each character in a new standard table parallel to the ASCII character set.

The given picture in the 7*5 array of LEDs represents the letter H. To save such picture for each character is not so simple, converting these pictures to lows and highs in the output pins also raise questions towards easiness. The easiest way that can be adopted here is to consider each columns as 7 bit binary and let us code to be an array of such values succeeded by a zero indicating the end of the character ( this will help us to generate the length of the meassages dynamically and ease our job later on).

Ie let us consider the H as, here as per our method of coding each vertical column is considered as a 7 bit binary and this can be considered as an array-{127,8,8,8,127,0} where the last 0 represent the end of the character and each other numbers represent the respective vertical column converted to decimal. As it is H the place of LSB or MSB doesn’t make any change but in general the bottom bit is taken as the LSB. Thus the entire ASCII set can be coded to this coding method. With this new character set of numbers instead of characters we can simply make any message into its corresponding integer array which will be a long array of integer where each character is replaced by its code and as each character is ending with zero there will be a single line in between each character (ie if the message is HELLO the corresponding display array is-{127,8,8,8,127,0,127,73,73,73,73,0,127,1,1,1,0,127,….}).

Now what all needed is a circuit that can display our messages.

Here one thing is sure that how ever we may design the display, it should have height of atleast 7 LED. The length is taken as 32 as the vertical lines can be controlled by 5 bits through a decoder. Now we have a display board of 7*32 in size, which is controlled by vertical and hirizontal lines. The parallel port of a computer can provide a total of 12 outputs through two ports (8 from port-0x378 and 7 control outputs from port-0x37a ) exploiting this we can take 7 these outputs to control our 7 horizontal lines of the display board, the rest 5 pins can be used to controlled the vertical line as we have said earlier.

Consider the two simple for loops given below ,

for(i=0;i<32+length;i++)

for(l=0,j=i;j>=0;j--,l++)

if(j<32)

if(l

board[j]=message[l];

else

board[j]=0;

in which meassage [] is the array that contains the coded meassage(say the message is HELLO then meassge[]={127,8,8,8,127,0,127,1,1,1,0,127,1,1,1,0,…..}), length be the length of the array- message[], and board be an array of size 32 which is initialised to all zeros. In this loop the array board gets changed and it changes as,

and so on…

Let us call each of these boards as different clips now what we have to do is to show these clips at rate not slower than 16 clips per second.

Here its very easy to display the first clip, only one vertical line has to be selected so it is enough to pass a value = 0 to the 5 pins, controlling the vertical lines and a value = 127 to the 7 pins, controlling the horizontal line thus the 0^th vertical line is selected and it will show 127 (binary for 127 is 1111111 ie all the 7 LEDs are lighted up ) . Now second clip should be shown, but it is not as simple as the first clip at the first sight as here we have to show two vertical lines simultaneously, one with value 127 and another with 8. And in the 3^rd clip there are 3 vertical lines to be activated and so the number of lines to be activated simultaneously increases with the value of I in the above loop also in some message for some value of this I there may be some state that all the 32 lines should activated simultaneously with a decoder controlling the vertical lines !!!. Here comes the need for the principle of showing the individual lines one by one in short time and repeating it to a certain time (through which we have gone at the top). That is values 0 to 31 is passed to the 5 pins one after the other repeatedly for some time and each time if the value ‘n’ is passed to the 5 pins then the value corresponding to the column ( board[n]) is passed to the 7 pins that controls the rows. Thus it will appear that all the 32 lines are activated with their values simultaneously. Now the matter is only to change the clips just in a time equal to the persistent of vision so that the clips will appear to have a flow. This can be done by adjusting the time to show each clip.

INTER FACING THE PARALLEL PORT

Interfacing of parallel port in the circuit is very simple as all the pins are going to different points in the circuit and none of the pin is multiplexed. But there is one thing which is to be considered with a little care that here in the display board we are using 12 output pins in which 4 are the control outputs in which the 3^rd pin alone is active high and the rest 3 are active low. This can be cleared by just adjusting our code, passing ‘n^11’ instead of n to the 5 vertical controlling pins will fix this issue.

INTER FACE WITH MICRO CONTROLLER

Adding a micro controller interface to the circuit made it more compact and convenient. The ATMega16 micro controller which have 4 i/o ports is used here in which port A controls the rows, port C controls the vertical columns through the decoder. We have added something more to the circuit here we have included a decimal to binary priority encoder to the circuit whose inputs are controlled by 9 switches in the board and its outputs are passed to the port D of the micro controller. The addition of input to the micro controller opened the door way to save 10 messages in it at a time and each of which can be selected using the switches which are connected to the inputs of the encoder whose output controls the micro controllers input.

Here is the sorce code

Hi friends

yes here starts a another one ...............................