Sour Swinger Predominantly follows my Army & Iraq Deployment. Also has some Geek, School, and other talk.

The last programming assignment in my operating system’s class was to write a simulated file system for linux via system calls.  Basically we had to implement a read and write call for storing data via a file name. Persistence was optional.  Since my time was short, I left out persistence.  Basically all I wrote was a hash.  Write accepts a file name and string of contents or another words a key and value and stores it in a hash table.  Read accepts a file name/key and returns the string of contents/value.  Its fairly simply and provides a good example of utilizing a hash in C.  As for being a true simulated file system….far from it.

I used Horner’s algorithm to hash.  Collisions are handled by chaining.  Each table element is a struct consisting of a pointer character array and a pointer to the next collision struct.  I did not implement any rehashing or resizing of the table.  This is a very basic hash example.  Keep in mind this is not the code for implementing the hash with syscalls in linux.

Download Horner Hash.

There are two different methods to quickly square any two digit number. The one I’m about to show you is by far the easier since it eliminates any complex multiplications. I’ll do the other method in a different post. Lets look at our first example:

43² =
4 (3²) =
(4 × 3 × 2) 9 =
4² (24) 9 =
(16 + 2) 49 =
1849

We should always work from right to left since we need to worry about carrying. First we squared the last digit, 3. This gave our last digit of the answer, 9. Next multiply the original two digits 4 and 3 and double the answer. That gave 24 which means we had to carry the 2 into the next step. Finally, we squared the original first digit, 4, and added anything carried over from the previous step, 2. Our final answer 1849 has been found.

Thats basically it. The only thing that could happen different is the first step will end up needing to carry. Lets try another example for that situation:

39² =
3 (9²) =
[(3 × 9 × 2) + 8] 1 =
3² (62) 1 =
1521

Once again, we started on the right and squared the 9. This gave us 81 which means we had to carry the 8 over to the next step. The remaining 1 became the last digit in our answer. Then we multiplied the original two digitis 3 and 9, doubled it, and added what was carried over from the first step, 8. This gave us 62 which meant we had to carry again, leaving the 2 as the next digit in our answer. Finally we squared the 3 and added the carry which gave 15. Our final answer 1521 has been found. With a little practice, you can get pretty quick at this.

Surprisingly there’s a quick method to multiplying numbers by 11.  Of course the larger the number gets, the harder it becomes.  There’s a simple pattern to follow when totally up the answer.  It’s best to slowly work up to exposing the pattern then to dive straight in.  It’s also easier to show rather then explain the pattern.  Lets start with a two digit number:

24 × 11 =
24 =
2 __ 4 =
2 (2 + 4) 4 =
264

We first drop the whole “× 11″ as that part is no longer important to remember.  Looking directly at the 24, split it apart and place the sum of its digits in between.  That’s it.  The pattern isn’t noticeable yet.  Before we move on to three digits lets look at a special case:

49 × 11 =
49 =
4 __ 9 =
4 (4 + 9) 9 =
4 (13) 9 =
(4 + 1) 39 =
539

That looks worse then what it is.  We did the same thing as before.  Ignored the “× 11″ part, split the 49 and summed the digits.  However this time the sum yielded a two digit number, 13.  All you do is carry the one over to the four.  Just like you would in normal addition.  Lets try a three digit number:

314 =
3 __  __ 4 =
3 (3 + 1) (1 + 4) 4 =
3454

I didn’t bother writing the “× 11″ since we always ignore that anyway.  We split the number up again, but this time left space for two more numbers.  How does one know the number of additional digits to add?  Its always 1 minus the total number of digits.  So if we had a number with 10 digits, we’d be adding 9 more numbers.

Here’s where the pattern starts to show.  All you do is work your way across the original number starting from the right.  Add all the pairs of numbers that are next to each other.  Still don’t see it?  Lets try a longer number a little bit slower:

12345 =

We’ll start from the right.  Remember, add all the pairs of numbers whom are next to each other.  So the first pair is (4 + 5).  Now move one and add the next pair (3 + 4).  Then (2 + 3) and finally (1 + 2).  All together, it’ll look like this:

1 (1 + 2) (2 + 3) (3 + 4) (4 + 5) 5 =
135795

See the pattern now?  Once numbers start getting this long, its hard to do in your head especially if carrying is involved.  However this makes for a fast and easy computation on paper.

A bit ago I talked about a multiplication trick that involved halving one number and doubling the other.  The only stipulation was that one of the numbers had to be even.  What if both your numbers are odd?  Is it still possible?  Of course!  Its just a little more involved and probably not something you can strictly do in your head.  However its still fun to see it in action.  Lets try one:

113 × 27 =
56  × 54 =
28 × 108 =
14 × 216 =
7 × 432 =
3 × 864 =
1 × 1,728 =

Notice I did the same thing as if one of the numbers were even.  Just pick one to half and the other to double.  When you half an odd number, simply ignore the remainder.  We’re not done yet as 1,728 is not the correct answer.  Remove those numbers whose halved number is even.

113 × 27 =
56  × 54 =
28 × 108 =
14 × 216 =
7 × 432 =
3 × 864 =
1 × 1,728 =

Now, sum all the remaining numbers that were doubled.  Do not include those numbers that were halved.

         27
       432
       864
+ 1,728
   3,051

And that’s your answer!

Intro
Holy Shit! I finally finished this damn thing. LoL. Following last years coding competition, I decided to write a sprite editor for this years event which actually starts today. Talk about last minute. I got half way, and put it on the back burner a few months ago. Check out more about it here. I choose to write my own editor because the GIF conversion examples I found proved more of a burden then what it was worth. With my editor, I have tight control over how I implement things. Besides, I’ve never done anything this advance in QBasic before. Helps learn the whole graphics process better.

Included in this post is a small talk about both the sprite editor and and the demo program, as well as instructions on using them properly. Scroll to the bottom of the page to simply download everything. Unfortunately, I couldn’t get the source files to compile so you’ll have to run the program through the IDE. If anyone can supply me with the compiled versions, that’d be great. Since all this was rushed, there’s a good chance you’ll find a bug. Let me know of any you may spot.

GFX Editor
Supports only SCREEN 13. This was chosen due to the 256 color support. Max sprite size is 72×64. I included my own custom PALETTE. You may plop your own in, simply change the SUB SetPalette. Some modifications may then be needed to SUB UpdatePaletteGradient. Mouse support is also included.

Does NOT support saving multiple images into one file for animation purposes. Ran out of time to implement.

My custom PALETTE supports 15 shades of the following colors: grey, red, orange, brown, yellow, chartreuse, green, spring green, cyan, azure, blue, purple, magenta, and fuchsia. It also supports dynamic PALETTE changing based off a 30 FPS (Frames Per Second) display. There are 15 fading and 15 blinking colors derived off the main colors mentioned above. Three colors are reserved (0, 14, 255). For transparency, 0. For the grid color, 14. For the mouse, 255. Colors 3 through 13 are unused and can add additional custom colors to them.

Please note, I basically rushed this in the last few days because the competition is today. The coding style is HORRIBLE and not a good example of proper techniques nor how to accomplish certain things. Though check out SUB SaveImage for how I utilized BSAVE.

The editor has a very basic layout. The PALETTE to select your colors is on the bottom right hand side of the screen. The thumbnail of what the image will actually look like can be seen at the top right of the screen. The entire screen to the left is the actual grid to draw your graphics. Your mouse will turn to whatever color is selected to be painted with.

Left Click: Selects color when over PALETTE. Paints color when over grid.

Right Click: Erases color when over grid square. (Paints the transparency color).

f: Flips between the two PALETTEs to select colors from. This was done to save on space.

i: Displays info about the current image.

n: Create new image.

y: Save current image before starting a new one.
n: Don’t save current image, just start a new one.
c: Cancel new image selection.

1 to 72: Sets new image width.
-1: Cancels new image selection.

1 to 64: Sets new image height.
-1: Cancels new image selection.

l: <-(lower case “L”) Loads an existing image.

y: Save current image before loading.
n: Don’t save current image, just load new one.
c: Cancel load selection.

s: Saves current image.

If not saved yet, will ask for file name first.
y: Saves image.
n: Erases file name (NOT the file), recalls saves selection.
c: Cancels save selection.

-: Decreases current color selection by one shade.

=: Increases current color selection by one shade.

[esc]: Terminates program.

GFX Demo
Demonstrates good programming techniques since its meant to show how to utilize the saved graphics from the editor. Too lazy for comments. LoL. Any questions, let me know.

Supports SCREEN 13 with double buffering (via a virtual screen/page) to eliminate flicker. Supports utilizing the transparency color as well as the dynamic PALETTE changing. Displays images at a rate of 30 FPS.

Does NOT demonstrate animation. This program’s sole purpose is to show how to BLOAD said graphics and PUT to the screen. Animation is the easier part.

First hit “l” (lower case “L”) to BLOAD the graphics from hard disk. Then hit “p” to PUT images into the virtual page. Since the screen is continuously updated, the graphics will quickly display to the screen automatically. I separated the steps to allow easier understanding of the process. Hit [esc] to quite.

Files
Be advised, when loading the GFX Editor use the following command to start the Qbasic IDE: qb.exe /L qb.qlb

This is needed for the mouse routines to work. Without you won’t be able to run the program. Included in the zip is GFX Editor and GFX Demo along with needed example graphic files. I also included the qb.qlb file for those that may be missing it.

Zipped File: GFX Editor v08.410

I cdnuolt blveiee htat I cluod aulaclty uesdnatnrd waht I was rdanieg. The phaonmneal pweor of the hmuan mnid. Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.