Help with memorymapping

[steffi]

Hi!

I have to do an emulation of a hardware and have a description of which registers they use in the hardware.

But in my emulation I only need some of the registers with addresses like for example

0x00
0x04
0x0C
0x10
0x1C

(there are spaces between some of the addresses for example 0x10 - 0x1C, two are missing because you are counting forward with 32 bits so 0x14
and 0x18 are missing)


I can do a mapping in the following way:
One array with 8 elements

Arr[0] = 0x00
Arr[1] = 0x04
Arr[2] = 0x08
Arr[3] = 0x0C
Arr[4] = 0x10
Arr[5] = 0x14
Arr[6] = 0x18
Arr[7] = 0x1C


This means that Arr[2], Arr[5], Arr[6], takes up space but are never used

I need appoximately 100 registers (from 0x00 - 0xe09) and if I do the mapping in this way I should need an array with 900 elements.

Does anyone have an idea how to solve this in a beautiful way? =(

[IceDane]

If you were to use an array of 900 elements, how would you distinguish the valid registers from the invalid ones? If you do indeed have a way of doing that, you have a pattern. If you have a pattern, you can use that pattern to put only the registers that are valid in the array.

[whiteflags]

I have to do an emulation of a hardware and have a description of which registers they use in the hardware.

But in my emulation I only need some of the registers with addresses like for example

0x00
0x04
0x0C
0x10
0x1C

Ok, but it seems like you would want to actually provide some space as well so it's more than just a bunch of addresses and it might act like actual RAM.

I was thinking maybe:

struct mem {
   const unsigned int address;
   unsigned int space;
}
my_map[] = 
{
   { 0x00, 0},
   { 0x04, 0},
   { 0x08, 0}, 
   { 0x0C, 0},
   { 0x10, 0},
/* ad naseum */
};

After you've set up the addressing then you also actually have a space member to work with (to store whatever).

You're not going to really get away from arrays or lists if what you're really "emulating" is RAM.

[IceDane]

Ok, but it seems like you would want to actually provide some space as well so it's more than just a bunch of addresses and it might act like actual RAM.

I was thinking maybe:

struct mem {
   const unsigned int address;
   unsigned int space;
}
my_map[] = 
{
   { 0x00, 0},
   { 0x04, 0},
   { 0x08, 0}, 
   { 0x0C, 0},
   { 0x10, 0},
/* ad naseum */
};

After you've set up the addressing then you also actually have a space member to work with (to store whatever).

You're not going to really get away from arrays or lists if what you're really "emulating" is RAM.

I think his problem was more directed towards how he could automate the process of putting the registers in an array, instead of having to type out 100 registers manually.

[steffi]

Hi IceDane, thanks for you reply...

What I was planning to do was:
The register rx will have a place in the array rx/4
For instance, take register 0x08 its place in the array will be 0x08/4 = 2.

I can put them on the right place, but i will like to avoid having many empty elements in my array. So instead of having an array of 8 elements, I will like to have an array of 5 elements.

[matsp]

From what I can tell this is a problem of "speed vs. size".

If you "compress" your array to not have "holes" in it, then you need to use some form of "loop" or "hash" method to find the relevant entry, rather than just indexing with the number of the hardware register.

If you need to emulate this "at speed", you may want to consider wasted space less wasteful than wasted CPU cycles to search for an entry - that will of course ALSO depend on how often the hardware registers are accessed.

--
Mats

[steffi]

Hello Citizen.

I will like to do my mapping in order to do this, read(address) write(address, value) thats why I need those register. I dont know how to solve that problem, I don't know if it is ok to have empty elements in a long, long array.

With your map... how can I access one specific register? i am just starting with c :-(

[steffi]

That is exactly my dilema matsp... I have to access my register quite often... what is more efficent, having a big array with empty elements or running loops every time i need to access the data?

[QuantumPete]

That is exactly my dilema matsp... I have to access my register quite often... what is more efficent, having a big array with empty elements or running loops every time i need to access the data?

Big array with empty elements. To access one is very simple, taking just O(1).
Searching for one, using a binary tree, say, would take on average O(log n).

QuantumPete

[steffi]

Thanks QuantumPete. Now I wonder if there is some kind of math-magic so that I can have an array of the size that is equal to the number of register that I need and that can easily be accessed?

[whiteflags]

Hello Citizen.

With your map... how can I access one specific register? i am just starting with c :-(

Access the array.

my_map[addr_you_want / 4]

considering that 0x04 is in slot 1, 0x08 is in 2, ... there is an obvious arithmetic series here. Every new address is a multiple of four.

If you want a data structure of flexible size, you can still use my model if you so desire. The only real work comes in when you build new maps and have to assign unique addresses. You'd lose out on const members if you need to build more than one huge map. But I'd do something like this in that case

struct mem {
	unsigned int address;
	unsigned int space;
};


#include <stdlib.h>
#define MAP_SIZE  900uL

struct mem *new_map( void )
{
	struct mem *my_map = malloc( sizeof *my_map * MAP_SIZE );
	if( my_map ) {
		static unsigned int idx = 0;
		unsigned int count;
		for( count = 0; count < MAP_SIZE; count++ ) {
			my_map[count].address = idx * 4;
			my_map[count].space = 0;
			++idx;
		}
	}
	else {
		return NULL;
	}
	return my_map;
}

[steffi]

Thank you very much for all your help, you were all so nice I wasn´t expecting such as quick and useful answers, I will be soon posting more questions. I am working with an emulator and unfortunatlly i dont know much about this. Thanks again for all your help

[IceDane]

For an even faster access to the register, you can use the bitwise right shift operator, and shift by two bits. It doesn't really matter unless you're accessing the registers A LOT (As in, a million times or something).

EDIT: Thought a bit of clarification was in order.

Anyway, instead of doing something like:

printf("Register contains: 0x%x\n", array[register / 4]);

you'd do:

printf("Register contains: 0x%x\n", array[register >> 2]);

The difference in speed won't be noticeable if you're only doing accessing the registers a few times, but it will if you're doing it in the hundreds of thousands - Like I said before.

[matsp]

For an even faster access to the register, you can use the bitwise right shift operator, and shift by two bits. It doesn't really matter unless you're accessing the registers A LOT (As in, a million times or something).

Most decent compilers will convert divide & multiply to shift operations when possible.

--
Mats

[IceDane]

Most decent compilers will convert divide & multiply to shift operations when possible.

--
Mats

Ah, I didn't know that, actually. Does GCC do that, by default? Or do you need to use optimization switches?