Adding 64-bit values using 32-bit registers

Last week, I published a post discussing how to left shift 64-bit values using the available 32-bit sized registers on MIPS. This week, we thought I should do something similar which is to provide you with another article that describes a technique that solves another interesting problem. This time I will discuss how to add two 64-bit values. This may not seem difficult at first, however we must remember that MIPS processors do not have carry flags. We need the carry flag (or something equivalent) to preserve the result of an intermediate computational step. What we have to do is somehow simulate ‘Add with carry’ without the carry to allow for the addition of 64-bit integers using 32-bit registers.

Adding two 32-bit values is trivial since the operands and the result can be contained in single registers, so here we can just use a simple ‘add’ instruction, therefore carry is not needed. The sizes of the operands for the addition instruction are either 32 or 64 bits but in order to perform the addition, the sizes must match. An exception should be raised if the sizes are not the same. Before I discuss the method for adding two 64-bit values, let’s remind ourselves how signed and unsigned values are represented in 32-bit binary. The sign extension does not have an effect on the result of the computation due to the way two’s complement works, I only include it for completeness.

1

In the case of the unsigned values, the number of possible integer values goes from 0 to 232 and they are all positive, however if we want to represent signed integers in 32 bits then we need to use one bit, the most significant bit, to represent the sign, so we can represent both positive and negative integers in the range from 0 to 231. A negative value is derived such that you take a positive integer then you apply the method of two’s complement to it. Let’s see an example how to convert a positive number to its negative equivalent in 8-bit binary representation.

Two’s complement:

0000 1010   # = 10
1111 0101   # invert bits
0000 0001   # add 1
1111 0110   # = -10

First you take the integer as a bit string then you invert all the bits and finally you add one to the result. Two’s complement can also be used to convert a negative integer to positive.

Adding 64-bit operands

The two 64-bit integer operands have to be stored in two registers each. The first operand is stored as $t1:$t0, while the second operand is loaded as $t3:$t2.

1.      Add low bytes

The first step of this algorithm is to add the two low bytes into $t4 which we will use as a temporary storage for this partial sum.

addu $t4, $t0, $t2

We use the unsigned operation because the low-bytes do not have a sign-bit as the upper bit! We also need a way to know if there is a carry from this partial calculation. For example if we add the following two binary numbers we get a result that cannot be represented in a single register (here I assume that the registers are 4 bits in size), i.e. there is a carry bit.

1111 + 0001 = 10000

What we can do here is to store the carry bit (the 5th bit if you like) in a temporary register in the next step.

2.      Simulate the carry flag

At this point we are going to use the ‘sltu’ instruction to store the carry bit in $t5.

sltu $t5, $t4, $t0

(Alternatively: sltu $t5, $t4, $t2 : either will do)

Here the ‘sltu’ instruction compares $t4 (sum of low bytes) with either of the individual set of low bytes ($t0 or $t2). The computation generated by the ‘sltu’ instruction goes like this. If $t4 < $t0 or if $t4 < $t2 then $t5 = 1, else $t5 = 0. It does not actually matter which set of low bytes we are using for the comparison because $t4 will always be smaller than any of the individual low bytes if there is a carry. But let me show you with some examples:

  1. $t0  =  0000
    $t2  =  0000
    $t4  =  0000       $t4 = $t0 = $t2         -> $t5 = 0

Here the computation does not generate a carry. We can see that $t5 has been set to 0 as required since $t4 is not less than either $t0 or $t2.

  1. $t0  =  0000
    $t2  =  1111
    $t4  =  1111       $t4 > $t0, $t4 = $t2    -> $t5 = 0

There isn’t any carry in this example either because $t4 is not less than either $t0 or $t2.

  1. $t0  =  0011
    $t2  =  0110
    $t4  =  1001       $t4 > $t0, $t4 > $t2    -> $t5 = 0

No carry because $t4 is not less than $t0 or $t2.

  1. $t0  =     0001
    $t2  =     1111
    $t4  =(1)0000       $t4 < $t0, $t4 < $t2    -> $t5 = 1

Now, in this example we do generate a carry, so let’s see if the method works. Remembering that $t4 is (for these examples) 4-bits in size, so the 5-th bit (the ‘1’) is lost: $t4 = 0000 because the carry bit is lost so, so $t4 < $t0 and $t4 < $t2 therefore $t5 is set to 1.

  1. $t0  =  1111
    $t2  =  1111
    $t4  =(1)1110       $t4 < $t0, $t4 < $t2    -> $t5 = 1

The last example works for the same reason as the previous one did.

Using my diagram above to visualise how numbers work, it is possible to see that no two numbers added together can ever wrap round over themselves, so the result will only ever be greater than either of the operands if there was no carry. The number system forms a cycle.

3.      Add high bytes with carry

Now, we need to add the two high bytes ($t1 and $t3) plus any carry that is left from the addition of the low bytes and store the result in $t1.

addu $t5, $t5, $t1      # $t5 = carry + $t1(high bytes of operand 1)
addu $t1, $t5, $t3      # $t1 = $t5 + $t3(high bytes of operand 2)

Finally we move the sum of the low bytes into $t0.
move $t0, $t4           # move partial sum to $t0

At the end of the process we have a result as a 64-bit value stored as $t1:$t0.

I hope you found this article helpful. See you soon…

Roland

 

Left shifting 64-bit values using 32-bit registers

Yesterday, while working on the implementation of the left shift IL operation (shl) for MIPS, we came across some challenges related to shifting 64-bit values using 32-bit registers. The solution is a bit tricky, so we thought it would be useful if I produced an article discussing how it can be done.

In order to shift a string of bits, we need two operands; the data itself and a value specifying the distance we want the data to be shifted. The shift value can either be a constant or a value stored in a register. Although in this article we assume that the values are in registers, the same technique can be adapted to be used with the assembly instructions that use constant values. There are four different cases we need to consider in terms of operand sizes:

  • 4-byte data, 4-byte shift value,
  • 4-byte data, 8-byte shift value (this is unsupported by C#),
  • 8-byte data, 4-byte shift value,
  • 8-byte data, 8-byte shift value.

The 4-8 case is unsupported by C#, so in this scenario the compiler throws an exception. The 4-4 case uses a single left shift assembly instruction (sllv) so there isn’t much explanation needed there.

8 – 4 case

In the 8-4 case, the 8-byte sized data is shifted by a value that is represented by a 4-byte binary number. Since we only have 32-bit (4-byte) registers, we need to store the data in two separate registers. One register contains the low bytes ($t0) while the other contains the high bytes ($t1). In this example, I store the shift value in $t2.

1

2

Consider a 1-byte left shift, i.e. $t2 contains the value of 8. Now we have a problem because the top byte of $t0 must replace the bottom byte of $t1 as well as the rest of the data must be shifted correctly. So how do we shift an 8-byte value using 4-byte registers? I will show you how by going through some examples. There are two variations of the 8-4 case; one where $t2 < 32 and another where $t2 >= 32.

The method ($t2 < 32)

Let’s say we want to left shift this data by 1 byte (1 byte can be represented by two hexadecimal digits):

3

Somehow we want the result to end up looking like this:

4

1.      Left shift high bytes by $t2

First, we want to left shift the high 4 bytes ($t1) of the original data by the value carried by $t2, which is 1-byte. The low 4 bytes remain unchanged for now. So we have:

5

2.      Right shift low bytes by (32 – $t2) into temporary

The next step is to logical right shift (not arithmetic right shift!) $t0 by (32 – $t2) into a register which we will use as a temporary storage, say $t4. Since $t2’s value in bits is 8, we right shift $t0 by 24 into $t4. This way we get the proportion of $t0 which we then want to copy into $t1. $t0 and $t1 remain unchanged at this point.

6

 

3.      OR temporary with high bytes

Here we can combine $t1 and $t4 using the logical OR operation to get the correct result for the high 4 bytes which we store back to $t1.

7

 

4.      Left shift low bytes by $t2

There is only one thing to do, left shifting the low 4 bytes ($t0) by $t2.

 

8

Now the algorithm is complete. If we compare this result with the desired result above, we can see that they are identical.

The method ($t2 >= 32)

If $t2 >= 32 then we are left shifting the data by 32 or more bits which means that the least significant bit (little endian) of the data is pushed beyond the low bytes into the high bytes. In all cases where the shift value is greater than or equal to 32, $t0 ends up filled with zeros and the content of $t1 are lost completely. But in what form does $t0 take over $t1? Let me show you step-by-step as before. Now let’s assume that we are left shifting by 40 bits and we have the same original data as before.

 

3

But this time we want the result to be this:

9

 

1.      Move low bytes into high bytes

We copy the contents of the low bytes into the high bytes. We do this to save the contents of $t0 into $t1. The original data becomes:

10

 

2.      Fill low bytes with zeros

Since the data is pushed all the way beyond the low bytes, we can fill the $t0 with zeros.

11

 

3.      Left shift high bytes by ($t2 – 32)

The final step is to left shift $t1 by ($t2 – 32) which is 8 in our case. So the desired result is achieved as expected.

12

 8 – 8 case

In the 8-8 case, both the data and the shift values are 8 bytes in size. There is one important observation we must make; shifting a 64-bit value by 64 bits or more is pointless since the result will always be zero. We also know that the number 64 is represented by this binary number: 0b0100 0000 which can easily be contained in the low bytes of the shift value ($t2). Actually any non-zero value beyond the 6th bit would yield a zero result but let’s just consider 4 bytes to be the smallest size we can manage.

 1 

13

To conclude, if $t3 is non-zero then the result of the left shift will definitely be zero, while if $t3 is zero then we can proceed the same way as in the 8-4 case by simply ignoring $t3.

I hope you found this article helpful. Please leave a comment if you think I missed something or if you have anything to add and I will do my best to respond.

See you around.

Roland

 

The bug that went undetected for over a year…

Yesterday I announced that:

Just fixed a bug which has existed since the first week that I wrote FlingOS – so excited!!

I promised a blog post would follow, so here is that blog post – it’s going to be a good one. So sit back, relax and read on as I take you through the history of this bug.

When I first started writing FlingOS I had somewhere between no idea and less than no idea what I was doing. Seriously, all I knew was the structure of a C# to native compiler – I had worked on Cosmos for about 5 months but for various reasons I decided I wanted to write my own C# OS, with a different structure. I had my own compiler working relatively quickly and the next step was to implement basic features that would underpin the entire OS.

It’s probably reasonable to say that if something is going to underpin your entire system, you want to get it right, lest it have any nasty, invisible side effects later on. One such underpinning component was the Heap. Ahh the Heap… The heap implementation has caused much confusion and difficulty. This is not because a heap is difficult to understand or use, it’s just fiddly and crops up all over the place such that slight errors kill the entire OS. Some such errors have included not using spin locks (after I introduced multi-threading a few months back) and not allocating the heap enough space. (The heap space use to be allocated in the .TEXT section of the code! 120MiB .ISO files ;D With the new drivers compiler I shifted it to .BSS where it should be.)

When I first looked at implementing a heap, I wasn’t too interested in the internal workings. I knew what a heap did, I knew there were lots of ways of implementing them, each with pros and cons. I just wanted something simple and easy that I could use. Of course, FlingOS being one of only three active C# operating systems worldwide, there aren’t many (if any) suitable heap implementations floating around. However, there are lots of samples in C. The one I lumped for was a simple one from OSDev.

Over time I have adapted and updated the implementation to add things like allocation on or avoiding a boundary (as required by USB). The main Alloc function, however, has remained the same. Entirely the same. And this is where the issue lies. Early on in my development I found that with a 10MiB heap, my OS regularly seemed to run out of allocatable memory resulting in seemingly random page faults. My somewhat ignorant solution at the time was? : Make the heap 100MiB! This seemed to fix the problem, even though 90% of the heap was never allocated.

As time has gone on, page faults have appeared and disappeared sporadically until recently when I started trying to read large files from USB sticks. This used a lot of heap memory and suddenly the page faults were happening all the time. Not having really had to deal with page faults before I had no idea what was causing it. My instinct said that a page fault is due to unmapped memory, so something must be allocating an invalid pointer. But the heap wasn’t anywhere near out of memory. Unfortunately, with so many compiler changes going on in the past few months, there was no consistency to the issue. Even in the past few days the faulting address (or even instruction address) was not reproducible. It was seemingly random.

I investigated everything from interrupts to memory leaks to who knows what trying to trace this. Eventually I realised I wasn’t going to be able to unless I had a better view of two things:

  1. The sequence of events which lead to the page fault (and subsequent crash)
  2. The layout of all memory so I could see where things might be going wrong

For point (1) I had previously just outputted stuff to the screen through FlingOS’s BasicConsole class. But this wasn’t enough. I needed traceability and the ability to go back more than  a screen’s worth of information. So I implemented a new Serial class and hooked into the BasicConsole to redirect the output to a file on my host machine. As it turns out, I never needed to implement anything for point (2) – I realised what was going on before I got that far.

I realised the issue was to do with USB code, so I turned on all the trace code for the USB stack and inspected the output. The output contained the key piece of information : virtual and physical addresses of the memory the heap was allocating. They were invalid. They were valid addresses, but they didn’t fit inside the heap’s allotted block of memory! They were overrunning the end of the heap. I’d found my one, consistent piece of information.

Naturally I went looking for what could be overwritten by code writing to space beyond the end of the heap. Sure enough, immediately the heap memory were the unprotected page tables. And because USB uses physical addresses, there was no way I could have protected the page tables. I tested by allocating padding space between the page tables and the heap – sure enough the code took far longer to crash.

So the issue was in the heap. But the OSDev implementation looked pretty solid and many people had tested it. So I must’ve converted the code incorrectly to C#.  In the 18 months I’ve been doing low-level programming my understanding of pointers and pointer manipulation has grown – a lot. I went back to look at the heap in detail and found this spurious line of code:

void* result = (void*)(x * b->bsize + (UInt32*)(&b[1]));

This line of code is supposed to calculate the address of a block (x) with block size (b->bsize) and offset from the start of the heap (&b[1]). For those who understand pointer arithmetic they will easily see my mistake from when I converted the code – UInt32* will result in the pointer being multiplied by 4 (because UInt32 is 4 bytes in size). In my defence, however, the original line of code was thus:

return (void*)(x * b->bsize + (uintptr)&b[1]);

I asked a number of experienced programmers what they would expect uintptr to be a type for and all but one said: pointer to a uint (i.e. UInt32*). Only one was able to give me the actual definition (as per C99, which I found online) which is:

In C99, uintptr is “an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer”.

Great…so uintptr is not UInt32* it is in fact just UInt32 in C#.

Here’s a few caveats for those pedantic types amongst you:

  • Yes, pointers can be 8, 16, 32 or 64-bit. So it shouldn’t be UInt32 it should be some other form of UInt that allows agnostic size. However, FlingOS is entirely a 32-bit OS and C# doesn’t have a useful equivalent for uintptr (see next point).
  • Yes, C# has an IntPtr type – but it is intended for managed pointers and doesn’t play easily with most of the low-level code I’m trying to write for FlingOS. I may start using it in future, I may not. It might need some compiler updates to support it.

Detecting ATAPI drives

In the past few days I’ve been tackling a problem I’ve had for a while now – how to make ATAPI detection and retrieving device information reliable. I found that if I confined myself to a virtual machine then the existing code was pretty stable. However, with the large range of real-hardware I now have available to me, “it works in a VM” just wasn’t satisfactory. So I started testing and researching.

What I found was that I could reliably detect CD / DVD drives on all hardware. However, almost completely consistently, issuing the Device Identify Packet command resulted in the error bit being set. Yet my code worked exactly the same as many other people’s online examples. I reached the following conclusions:

  1. My code wasn’t doing something properly. It must be missing a step that would allow the ATAPI disc to respond properly.
  2. Other people’s code clearly hadn’t been tested on real hardware. There were various other indications of this which I won’t go into detail about here.

What I realised, however, was that once an ATA device has reported an error, it does not clear the error flag until you send it a new command. I also noted that part of the process of detecting an ATAPI disc, involves issuing the Identify command and then checking various registers to look for the PATAPI/SATA/SATAPI signatures. You check for the signatures even if the device reports an error.

So what was happening was some devices flagged up an error for the Identify command and some didn’t. The ones which did, required an additional command to be sent prior to the Identify Device Packet command otherwise it would still report an error. I went looking for a reset command and found one. Technically it only affects PATA/SATA not PATAPI/SATAPI devices. However, because it reset everything on the bus, and ATAPI devices have to be ATA responsive, ATAPI devices count this as a command. Thus issuing the Reset command clears the error flag. The problem was solved 🙂

Head over to this file on my dev branch in FlingOS’s BitBucket repository for sample Reset method code and usage.

Easy PXE Network boot

I had been meaning to set up a network boot system for FlingOS for a while. Yesterday I finally got around to it and after several hours of trying different software and solutions, I finally found one which worked nicely.

I had been meaning to set up a network boot system for FlingOS for a while. Yesterday I finally got around to it and after several hours of trying different software and solutions, I finally found one which worked nicely.

There is a modest selection of software out there which will let you set up PXE Network booting. The majority of it focuses around Windows installation and updating. What I needed was a system that would allow me to switch on any network-connected laptop and have it boot the latest version of FlingOS that I just compiled on my PC or main laptop. FlingOS already uses Syslinux as its bootloader so it made sense to use the Pxelinux variant of Syslinux. Unfortunately, Pxelinux requires something that most PXE Server programs don’t support – something called the tsize command.

PXE relies on a combination of DHCP, Binl and TFTP to allow a PC to detect the availability of a PXE server and to retrieve the boot image(s). Pxelinux requires that the TFTP server supports the unusual tsize command. “tsize” allows Pxelinux to request the size of a file ahead of time i.e. before it starts to retrieve it.

After various attempts using Serva and other software, I came across TinyPXE. Finally something that would work. TinyPXE was written by a guy who needed a simple, effective, no-install solution to running a PXE server. Perfect. It even comes with support for Pxelinux, Grub and others. What’s even better, is that it can auto-load everything from a human-readable config file. So once you’ve worked out what setup you need, you can just put it in the config file and never have to worry after that.

Here’s a copy of the contents of my config file (config.ini):

[arch]
;will over rule the bootp filename or opt67 if the client arch matches one of the below
00006=bootia32.efi
00007=bootx64.efi
[dhcp]
;needed to tell TFTPd where is the root folder
root=G:\Fling OS\Fling OS\Kernel\Kernel\bin\Debug\DriversCompiler\ISO
;bootp filename as in http://tools.ietf.org/html/rfc951
;filename=ipxe-undionly.kpxe
filename=pxelinux.0
;alternative bootp filename if request comes from ipxe or gpxe
; altfilename=menu.ipxe
;start HTTPd
httpd=0
binl=1
start=1
dnsd=0
proxydhcp=1
;default=1
bind=0
;tftpd=1 by default
;will share (netbios) the root folder as PXE
smb=0
;will log to log.txt
log=0
opt1=255.255.255.0
opt3=192.168.43.1
opt6=192.168.43.1
opt28=192.168.43.255
;opt15=
;opt17=
;opt43=
;opt51=
opt54=192.168.43.120
;opt67=
;opt66=
;opt252=
poolstart=192.168.43.121
poolsize=20
;alternative bootp filename if request comes thru proxydhcp (udp:4011)
;proxybootfilename=
;any extra dhcp options
;my gpxe / ipxe dhcp options
optextra=175.6.1.1.1.8.1.1
;the below will be executed when clicking on the online button
;cmd=_test.bat
;if log=1, will log to log.txt
log=1
[frmDHCPServer]
top=441
left=258

Rant of the week: MySQL Old Passwords

Description

Time for the rant of the week and this week it relates to the setup of this very blog. It was far from WordPress’s famous “5-minute setup” and here’s why:

Connect Error (2000) mysqlnd cannot connect to MySQL 4.1+ using old authentication

The full error message can be found below. This error message occurred when setting up the latest version of WordPress using MySQL, PHP and phpMyAdmin.

As with any technical problem, my immediate instinct was to Google this (after having read the error message of course). Sadly, I had no idea how to execute the suggested command and being part of shared hosting made that no easier. After some time Googling, the issue was clearly unresolved and had no clear answer. This page has a few more details about MySQL password hashing. So, here goes at my attempt.

Explanation

Simply put, this is a version compatibility issue achat viagra ligne. Version X of PHP doesn’t like working with Version Y of MySQL. But there is a solution and it IS what is written in the error message. It’s just fiddly to get it to work. Lots of online comments talk about the “old_passwords” variable being set. In fact, this is largely irrelevant. So here’s how to solve the problem.

Solution

You do may need to switch off the old_passwords variable (this only affects the current session so you don’t need super-user privileges) using:

SET SESSION old_passwords=0;

I was using phpMyAdmin (as that’s what my host provides). So, log in to phpMyAdmin, and ignore the “Change password” link – it won’t work. It doesn’t matter how many times you select to target version 4.1+ of MySQL, it still won’t actually use the updated hashing algorithm. The solution is to by-pass the phpMyAdmin logic entirely. From the home panel of phpMyAdmin (not within a database) open the SQL panel (link at top of the page).And then issue the command within the error message:

SET PASSWORD = PASSWORD(‘your_existing_password’);

The phpMyAdmin change password link actually issues the command with PASSWORD = OLD_PASSWORD(…) and hence the issue.

Full Error Message

Database connection fialed: mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication. Please use an administration tool to reset your password with the command SET PASSWORD = PASSWORD(‘your_existing_password’). This will store a new, and more secure, hash value in mysql.user. If this user is used in other scripts executed by PHP 5.2 or earlier you might need to remove the old-passwords flag from your my.cnf file