Bit Masking in a Cache

Question

In C I am attempting to separate an integer address value into the tag bit and the set index bit in a direct mapped cache with 4 sets. I do this so I can compare the correct tags at the line in the correct set of my cache. Here for example the address parameters:

• number of set index bits s=2
• number of offset bits b=3
• total number of address bits m=8

And in my example the address integer is 40 -- int address = 40.

• 40 in binary is 00101000
• The set index should be 01 = 1
• The tag should be 001 = 1

Instead for the tag I am getting 2 and the set index is 8 which have to be wrong because I only have 4 sets in my cache.

Here is how I am doing it, I am bit-masking the address to get the tag, which are the bits to the left of the set index up to the m=8 bit. And the set index is between the tag and offset bits which is the 01 in the middle of the 8 bit sequence.

• int tag = ((address & ~0 << (s + b)) >> 4)
• int set = (address & (~(~0 << s) << b))

I know I must be wrong but the more I try to write a mask the more I am getting confused and I must be forgetting something. I at least thought I was getting the tag right because the left bits should be easier than getting middle bits. Any advice or help would be greatly appreciated thanks a lot!

Answer 1

These equations will work for you:

tag = (address >> 5) & 0x7;
set = (address >> 3) & 0x3;

If you want to use the variables s, b, and m:

tag = (address >> (m-b))   & ((1u << b)-1);
set = (address >> (m-b-s)) & ((1u << s)-1);

In general if you want to extract N bits starting at bit i:

bits = (value >> i) & ((1u << N)-1);