Saturday, September 09, 2006

Primary Partitions.

Sometime we think how our harddisk(hdd) is partitioned. We may have certain partitions on our hdd which logically divides it into pieces. Well to simplify the things I will discuss only primary partitions here.

The first sector of the drive is called the Master Boot Record (MBR). You can read it with LBA = 0. For any new projects, you should not even worry about accessing a drive in CHS mode, as LBA just numbers the sectors sequentially starting at zero, which is much simpler. All IDE drives support accessing sectors using LBA. Also, all IDE drives use sectors that are 512 bytes. Recent Microsoft operating systems refer to using larger sectors, but the drives still use 512 bytes per sector and MS is just treating multiple sectors as if they were one sector. The remainder of this page will only refer to LBA address of 512 byte sectors.

The first 446 bytes of the MBR are code that boots the computer. This is followed by a 64 byte partition table, and the last two bytes are always 0x55 and 0xAA. You should always check these last two bytes, as a simple "sanity check" that the MBR is ok.

The MBR can only represent four partitions. A technique called "extended" partitioning is used to allow more than four, and often times it is used when there are more than two partitions. All we're going to say about extended partitions is that they appear in this table just like a normal partition, and their first sector has another partition table that describes the partitions within its space. But for the sake of simply getting some code to work, we're going to not worry about extended partitions (and repartition and reformat any drive that has them....) The most common scenario is only one partition using the whole drive, with partitions 2, 3 and 4 blank.

Each partition description is just 16 bytes, and the good news is that you can usually just ignore most of them. The fifth byte is a Type Code that tells what type of filesystem is supposed to be contained within the partition, and the ninth through twelth bytes indicate the LBA Begin address where that partition begins on the disk.

Normally you only need to check the Type Code of each entry, looking for either 0x0B or 0x0C (the two that are used for FAT32), and then read the LBA Begin to learn where the FAT32 filesystem is located on the disk.

Few Type Codes which represent some filesystems are:

01 DOS 12-bit fat
02 XENIX root
03 XENIX /usr
04 DOS 3.0+ 16-bit FAT (up to 32M)
05 DOS 3.3+ Extended Partition
06 DOS 3.31+ 16-bit FAT (over 32M)
07 OS/2 IFS (e.g., HPFS)
07 Advanced Unix
07 Windows NT NTFS
07 QNX2.x (pre-1988)
08 OS/2 (v1.0-1.3 only)
08 AIX boot partition
08 SplitDrive
08 DELL partition spanning multiple drives
08 Commodore DOS
08 QNX 1.x and 2.x ("qny")
09 AIX data partition
09 Coherent filesystem
09 QNX 1.x and 2.x ("qnz")
0a OS/2 Boot Manager
0a Coherent swap partition
0b WIN95 OSR2 32-bit FAT
0c WIN95 OSR2 32-bit FAT, LBA-mapped
0e WIN95: DOS 16-bit FAT, LBA-mapped
0f WIN95: Extended partition, LBA-mapped
10 OPUS (?)
11 Hidden DOS 12-bit FAT
12 Compaq config partition
14 Hidden DOS 16-bit FAT <32M
16 Hidden DOS 16-bit FAT >=32M
17 Hidden IFS (e.g., HPFS)
18 AST SmartSleep Partition
19 Unused (Claimed for Willowtech Photon COS)
1b Hidden WIN95 OSR2 32-bit FAT
1c Hidden WIN95 OSR2 32-bit FAT, LBA-mapped
1e Hidden WIN95 16-bit FAT, LBA-mapped
20 Unused
21 Reserved
21 Unused
22 Unused
23 Reserved
24 NEC DOS 3.x
26 Reserved
31 Reserved
32 NOS
33 Reserved
34 Reserved
35 JFS on OS/2 or eCS
36 Reserved
38 THEOS ver 3.2 2gb partition
39 Plan 9 partition
39 THEOS ver 4 spanned partition
3a THEOS ver 4 4gb partition
3b THEOS ver 4 extended partition
3c PartitionMagic recovery partition
3d Hidden NetWare
40 Venix 80286
41 Linux/MINIX (sharing disk with DRDOS)
41 Personal RISC Boot
41 PPC PReP (Power PC Reference Platform) Boot
42 Linux swap (sharing disk with DRDOS)
42 SFS (Secure Filesystem)
42 Windows 2000 marker
43 Linux native (sharing disk with DRDOS)
44 GoBack partition
45 Boot-US boot manager
45 Priam
45 EUMEL/Elan
46 EUMEL/Elan
47 EUMEL/Elan
48 EUMEL/Elan
4a AdaOS Aquila (Default)
4a ALFS/THIN lightweight filesystem for DOS
4c Oberon partition
4d QNX4.x
4e QNX4.x 2nd part
4f QNX4.x 3rd part
4f Oberon partition
50 OnTrack Disk Manager (older versions) RO
50 Lynx RTOS
50 Native Oberon (alt)
51 OnTrack Disk Manager RW (DM6 Aux1)
51 Novell
52 CP/M
52 Microport SysV/AT
53 Disk Manager 6.0 Aux3
54 Disk Manager 6.0 Dynamic Drive Overlay
55 EZ-Drive
56 Golden Bow VFeature Partitioned Volume.
56 DM converted to EZ-BIOS
57 DrivePro
57 VNDI Partition
5c Priam EDisk
61 SpeedStor
63 Unix System V (SCO, ISC Unix, UnixWare, ...), Mach, GNU Hurd
64 PC-ARMOUR protected partition
64 Novell Netware 286, 2.xx
65 Novell Netware 386, 3.xx or 4.xx
66 Novell Netware SMS Partition
67 Novell
68 Novell
69 Novell Netware 5+, Novell Netware NSS Partition
70 DiskSecure Multi-Boot
71 Reserved
73 Reserved
74 Reserved
74 Scramdisk partition
76 Reserved
77 M2FS/M2CS partition
77 VNDI Partition
80 MINIX until 1.4a
81 MINIX since 1.4b, early Linux
81 Mitac disk manager
82 Prime
82 Solaris x86
82 Linux swap
83 Linux native (usually ext2fs)
84 OS/2 hidden C: drive
84 Hibernation partition
85 Linux extended partition
86 Old Linux RAID partition superblock
86 NTFS volume set
87 NTFS volume set
8a Linux Kernel Partition (used by AiR-BOOT)
8b Legacy Fault Tolerant FAT32 volume
8c Legacy Fault Tolerant FAT32 volume using BIOS extd INT 13h
8d Free FDISK hidden Primary DOS FAT12 partitition
8e Linux Logical Volume Manager partition
90 Free FDISK hidden Primary DOS FAT16 partitition
91 Free FDISK hidden DOS extended partitition
92 Free FDISK hidden Primary DOS large FAT16 partitition
93 Hidden Linux native partition
93 Amoeba
94 Amoeba bad block table
95 MIT EXOPC native partitions
97 Free FDISK hidden Primary DOS FAT32 partitition
98 Free FDISK hidden Primary DOS FAT32 partitition (LBA)
99 DCE376 logical drive
9a Free FDISK hidden Primary DOS FAT16 partitition (LBA)
9b Free FDISK hidden DOS extended partitition (LBA)
a0 Laptop hibernation partition
a1 Laptop hibernation partition
a1 HP Volume Expansion (SpeedStor variant)
a3 Reserved
a4 Reserved
a5 BSD/386, 386BSD, NetBSD, FreeBSD
a6 OpenBSD
a8 Mac OS-X
a9 NetBSD
aa Olivetti Fat 12 1.44Mb Service Partition
ab Mac OS-X Boot partition
ab GO! partition
ae ShagOS filesystem
af ShagOS swap partition
b0 BootStar Dummy
b1 Reserved
b3 Reserved
b4 Reserved
b6 Reserved
b7 BSDI BSD/386 filesystem
b8 BSDI BSD/386 swap partition
bb Boot Wizard hidden
be Solaris 8 boot partition
c0 REAL/32 secure small partition
c0 NTFT Partition
c1 DRDOS/secured (FAT-12)
c2 Reserved for DR-DOS 7+
c2 Hidden Linux
c3 Hidden Linux swap
c4 DRDOS/secured (FAT-16, < 32M)
c5 DRDOS/secured (extended)
c6 DRDOS/secured (FAT-16, >= 32M)
c6 Windows NT corrupted FAT16 volume/stripe set
c7 Windows NT corrupted NTFS volume/stripe set
c7 Syrinx boot
c8 (See also ID c2.)
c9 (See also ID c2.)
ca (See also ID c2.)
cb reserved for DRDOS/secured (FAT32)
cc reserved for DRDOS/secured (FAT32, LBA)
cd CTOS Memdump?
ce reserved for DRDOS/secured (FAT16, LBA)
d0 REAL/32 secure big partition
d1 Old Multiuser DOS secured FAT12
d4 Old Multiuser DOS secured FAT16 <32M
d5 Old Multiuser DOS secured extended partition
d6 Old Multiuser DOS secured FAT16 >=32M
d8 CP/M-86
da Non-FS Data
db Digital Research CP/M, Concurrent CP/M, Concurrent DOS
db CTOS (Convergent Technologies OS -Unisys)
db KDG Telemetry SCPU boot
dd Hidden CTOS Memdump?
de Dell PowerEdge Server utilities (FAT fs)
df DG/UX virtual disk manager partition
df BootIt EMBRM
e0 Reserved by STMicroelectronics for a filesystem called ST AVFS.
e1 DOS access or SpeedStor 12-bit FAT extended partition
e3 DOS R/O or SpeedStor
e4 SpeedStor 16-bit FAT extended partition < 1024 cyl.
e5 Tandy DOS with logical sectored FAT (According to Powerquest.)
e5 Reserved
e6 Reserved
eb BFS (aka BeFS)
ed Reserved for Matthias Paul's Sprytix
ee Indication that this legacy MBR is followed by an EFI header
ef Partition that contains an EFI file system
f0 Linux/PA-RISC boot loader
f1 SpeedStor
f2 DOS 3.3+ secondary partition (Powerquest writes: Unisys DOS with logical sectored FAT.)
f3 Reserved (Powerquest writes: Storage Dimensions SpeedStor.)
f4 SpeedStor large partition
f4 Prologue single-volume partition
f5 Prologue multi-volume partition
f6 Reserved (Powerquest writes: Storage Dimensions SpeedStor. )
fa Bochs
fb VMware File System partition
fc VMware Swap partition
fd Linux raid partition with autodetect using persistent superblock (Powerquest writes: Reserved for FreeDOS. )
fe SpeedStor > 1024 cyl.
fe LANstep
fe IBM PS/2 IML (Initial Microcode Load) partition, located at the end of the disk.
fe Windows NT Disk Administrator hidden partition
fe Linux Logical Volume Manager partition (old)
ff Xenix Bad Block Table

The Number of Sectors field can be checked to make sure you do not access (particularly write) beyond the end of the space that is allocated for the parition. However, the FAT32 filesystem itself contains information about its size, so this Number of Sectors field is redundant. Several of Microsoft's operating systems ignore it and instead rely on the size information embedded within the first sector of the filesystem. (yes, I have experimentally verified this, though unintentionally :) Linux checks the Number of Sectors field and properly prevents access beyond the allocated space. Most firmware will probably ignore it.
The Boot Flag, CHS Begin, and CHS End fields should be ignored.

Monday, August 28, 2006

Counting no. of 1's in a given number without using loop.

Counting number of set of unset bits in a given 32 bit number is really a basic thing that may be used in number of lower level programming including kernel's memory management. I have used this in TAJ's memory manager routine to keep track of used and unused block of memory in my heap and page management. So this can be viewed as a simple bitmap that can be used to keep track of no. of resources.

Now this is really a mindblowing stuff I have ever came accrose. It is not that easy to count number of 1's (bit that are set) in a given number using loop. There are number of solution to this problem. For example:

1. int count=0;//x is input
return count;

2. int count=0;
if(n & 1)
n >>= 1;

etc etc etc.......

But what if you are not allowed to use loops in counting the number of ON bits? Well this is really mind boggling.. What to see the solution? Then please check it:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

1. Counting no. of ON bits in a 12-bit number.
c = (v * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

2. Counting no. of ON bits in a 24-bit number.
c = (v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL;
c += ((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL;
c %= 0x1f;

3. Counting no. of ON bits in a 32-bit number.
c = (((v & 0xfff) *
0x1001001001001ULL & 0x84210842108421ULL) +
((v & 0xfff000) >> 12) *
0x1001001001001ULL & 0x84210842108421ULL)) % 0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Isnt it mind blowing? But friends this things really works. Want to check the explaination why how it works? check this :

Torvalds vs Tanenbaum

We all know that Linux is a monolithic kernel and MINIX is a microlithic. Now this is really a hot flame war between creators of two most fascinating operating systems. Linus Benedict Torvalds and Andy Tenenbaum are really juming out of there nerves during 90's. <-- this is the link where you will find Dr. Andy and Mr. Linus getting out of there nerves.

Friday, May 12, 2006

How can you right your own Operatin System?

Well if you really wants to write your own OS then you must be sound in assembly. You must grasp the hardware specifican manuals.