Working with Bits and Bytes

*C · Bits and Bytes

---

Again long time since my last post. Anyway this is my personal stuff and no one is really reading it. Maybe Jurij and if you are reading this then let me know i buy you a Kebab. So jokes a side. While I worked on the problem to solve the 405 error when the client requests a url which is registered but with different methods I found a nice way to handle that situation. Its probably ( pretty sure ) not the best way but it is my way. Also one of those tricks is apparently introduced by Brian Kernighan.

Problem

As described above the client can request a path with a specific method but on the other hand the server can register the same path with multiple different methods. If the client requests it with a method with which it was not registered I need to send the client a 405 with the "Allow" header to tell the client what methods actually work for this path.

Initial - What first

So first of all the server at the moment handles multiple methods:

#define SAND_HTTP_UNKNOWN     0x00000001   // 0
#define SAND_HTTP_GET         0x00000002   // 1
#define SAND_HTTP_HEAD        0x00000004   // 2
#define SAND_HTTP_POST        0x00000008   // 3
#define SAND_HTTP_PUT         0x00000010   // 4
#define SAND_HTTP_DELETE      0x00000020   // 5
#define SAND_HTTP_MKCOL       0x00000040   // 6
#define SAND_HTTP_COPY        0x00000080   // 7
#define SAND_HTTP_MOVE        0x00000100   // 8
#define SAND_HTTP_OPTIONS     0x00000200   // 9
#define SAND_HTTP_PROPFIND    0x00000400   // 10
#define SAND_HTTP_PROPPATCH   0x00000800   // 11
#define SAND_HTTP_LOCK        0x00001000   // 12
#define SAND_HTTP_UNLOCK      0x00002000   // 13
#define SAND_HTTP_PATCH       0x00004000   // 14
#define SAND_HTTP_TRACE       0x00008000   // 15
#define SAND_HTTP_CONNECT     0x00010000   // 16
#define SAND_HTTP_ALL_METHODS 0x0001FFFF   // If we double SAND_HTTP_CONNECT by 2 then subtract one we get the ALL_Methods

So when the client sends a method somewhere in the code I iterate over the paths registered methods like this (imagen a for loop around it)

if ( memcmp( route->path, request->uri_view.data,
            request->uri_view.size ) == 0 )
{
// Path matches but method not remember method to later correctly
// assemble 405 info
con->methods_for_405_error |= route->method_int;
}

The important thing is the |= this is a way to remember which methods actually work with this path.

---

After that loop and oring all available methods i need a way to clamp the registered methods with the actually methods which work. But the server also already checks that when registering the path but yeah one little check more does not hurt anyone.

So how do I check that.

unsigned int bits = con->methods_for_405_error & SAND_HTTP_ALL_METHODS;
while ( bits )
{}

Its a quick AND operation everything outside SAND_HTTP_ALL_METHODS will be set to 0.

Simplified Example:
Registered Methods: 0x01101010
HTTP_ALL_METHODS : 0x0001FFFF
&
Result : 0x00001010

Two's Complement - Lowbit - Kernighan

Now lets check this part

while ( bits )
{
    unsigned int method = bits & ( -bits );

    sand_string_append( &con->buf_for_error_405,
                        sand_http_method_to_string( method ) );

    bits &= bits - 1;

    if ( bits == 0 )
    {
        break;
    }

    sand_string_append( &con->buf_for_error_405, ", " );
}
http_response_set_header( &con->response, "Allow",
                                con->buf_for_error_405.data );

As we see we will iterate over the bits set after our AND operation. And we see we that we append the method to our buffer. The function sand_http_method_to_string does what it says we give it a method (int) and it returns the string for it.

So now lets focus on the unsigned int bits & ( -bits ). What this does is it extracts one method of the many possible set ones. And now lets focus how it does it and for that lets focus only on the -bits part. Lets say bits is 0000 1010 which means the registered methods are GET and POST. The -bits is the two's complement what it actually is ~bits + 1

If we apply only ~bits we get 1111 0101 if we do only this then i guess its the one's complement but now if we add 1 we get 1111 0110 which how we can negate the initial value.

So great we have a negativ value now. The next part is lowbit extraction and how we can extract the lowest set bit. Which is the & operation
0000 1010
&
1111 0110
0000 0010

So great now we have the lowest bit and we can extract the string value of that method Nice :)

Now what? The loop is still going lets not forget our imaginary example had GET and POST set.

Now Kernighan comes into play. The line bits &= bits - 1 This gives us
0000 1010
&
0000 1001
0000 1000

And now the for loop continues because there is still one bit set. And also this way we can nicely set all methods for which this path is set.

---