C / C++ / MFC

19-Nov-04 0:25

I need to save information that has odd bit sizes, like 4,5,9,15 bits. I need them to save them in a file, so they use as little space as possible.

For instance, i have an array short, and i only need the value of the first 11 bit of each place in the array saved to a file.( In order to compress the file size). When it has all been saved it 0 pads the data, so it will be a multiplum of 8 bits.

Is there any standard libs, or other that does this.

(Its a school projekt on sound compression.)

Jack Puppy19-Nov-04 0:32

Jack Puppy

19-Nov-04 0:32

How about saving the array elements as short, then compress the data with zlib?

Pssst. You see that little light on your monitor? That's actually a government installed spy camera. Smile and wave to big brother!

Steve S19-Nov-04 0:43

Steve S

19-Nov-04 0:43

rikkemus wrote:
(Its a school projekt on sound compression.)

That's honest, at least, and more interesting than some of the project/homework questions...

OK. You have a short value (which is normally 16 bits), and you want to save only 11 bits. File writes must be a multiple of 8 bits (1 byte). Therefore, if you have only one short, you lose, since you can't write only 3 bits to a file, and have to write 16 bits in total.

However, if you have two shorts, you want to write 22 bits. You still lose, because you have to write 24 bits, not 22. However, that's better, since you now have only two redundant bits. Your strategy should be to pack the bits into characters for writing, and unpack them after reading.

This requires use of bit shift operators >> and << and the bit manipulation operations, and (&); or (|) and not (~).

If you know how many n-bit values you have then you need to write that out to the file too, so that you know how many to read Smile | :)

After that, you just stream the bits out. There's code that does stuff like this in the zlib/gzip stuff, but that might be a bit complex (I'm not meaning to patronise, but it's not the easiest stuff to understand).

Essentially, you start with an empty buffer. You add to the buffer the bits you want. Let's use 11 as an example. The buffer contains bytes. Lets number the bits from the first 4 values as 1 2 3 4 for illustration. After adding four values, you'd have

11111111
11122222
22222233
33333333
34444444
4444????

You just saved two bytes of storage over writing the short values directly.

You need to track which unused bits there are in the buffer, as on the next write, the buffer should contain

11111111
11122222
22222233
33333333
34444444
44445555
5555555?

and so on. This isn't necessarily the best way to 'compress' the data, since it's only removing redundant bits, and doesn't take advantage of any other encoding the way that something like MP3 does, but it's a start, and better than nothing. You can use something like zlib (in a DLL) and write the data as shorts, and that will probably give you bigger savings, but might not count as a success in your project Smile | :)

Steve S
Developer for hire

rikkemus19-Nov-04 1:16

19-Nov-04 1:16

Its divided up like this.
each set of information about the sound, have a header like this.

[0xFFF, 25*4 bit contains info about the number of bits used to represent a sound sample, 25*4 bit contains info about how much the data should be scaled.]

25*4 because there is 25 Bins that contains certain frequency, and 4 bit to represent the number of bits used. 0000 = 0 bit, 0001 = 2 bit, 0002 = 3 bit etc.

We cannot use standard compression methods like Zlib( im guessing its an algoritm like winzip? )

I was just hoping for a library allready made, that would put odd number bits into an array.
The library would do as you said, by putting the bits next after each other, since it cant write odd numbered bit count to a file.
It will become a simple compression.

Im just guessing someone might allready have made this kind of function allready.

Thx for the reply's

Bob Flynn19-Nov-04 1:14

Bob Flynn

19-Nov-04 1:14

Try to pack your data into the standard word size for your machine (32 bits for example). So for example if you have 15 bit values that you have to store, pack them into a 32 bit word by:
unsigned int a[] = {1023,2032};
unsigned int c[2];
unsigned int b;
a[0] = 1023;
a[1] = 2032;
b= (a[0]<<15)+a[1];
c[0]= b >> 15;
c[1] = b & 0x1FFF;

Be careful to pay attention to sign extention rules for your give compiler. This same procedure can be used for any number of bits.
In this case you still carry two bits of overhead, but it is very easy and efficient. If that is still not accpetable, you will need to write a slightly more complex algorithm that will allow you to place values across word boundaries.

Good luck with your project.

Henry miller19-Nov-04 2:14

Henry miller

19-Nov-04 2:14

I'm not sure if this will help, but look at your bits closely to see if a bit field can be used. This works best if your always access data in a definate pattern that fits into a struct well.

For instance if you had 4 bits you could do

struct myStruct {
BYTE a :4;
BYTE b :4;
}

Since you are dealing with 11 bits, something that simple won't work, but this might. Note that I managed to fit 4 different things into 6 bytes

struct myStruct2 {
short a :11;
short b1 :5;
short b2 :6;
short c1 :10;
short c2 :1;
short d :11;
...
}

Now you just need a class to access these, because b and c are divided up into two different shorts!

You also need to look into pragmas so that your strucutre is packed, otherwise you gain nothing.

#pragma pack(1)
// data
#pragma pack()

Last warning: your save file will not be portable to other systems! If your professor cares about this (and he should, but likely won't) you will have to use a different suggestion.

In the real world I would guess that this does not work very well. In the real world though we would use zlib, while in school there is good reason they don't let you use that. I'm offering this mostly as a learning exercise for you.

Bob Flynn19-Nov-04 2:34

Bob Flynn

19-Nov-04 2:34

This is another good way, and it is used in the "real world".

What makes it not portable is the fact that some compilers will store the bit field with the first data element starting at the LSB while another will place the first data element starting at the MSB.

So you would perhaps need header information to indicate the structure so that your code, no matter what platform it is compiled on, will properly interpret data that you read from a file.

BTW, I would use this method for simplicity before the method I suggested above.

rikkemus19-Nov-04 2:55

19-Nov-04 2:55

Thx, this is starting alot of ideas.

Just have a few questions.

As far as i understand, my struct :

struct MyStruct{
int b:3;
}
only allokates 3 bits of memory for this.

I use this command to write ->

if( (m_stream = fopen(m_fileName,"ab")) != NULL )
{
fwrite(dataPtr, sizeof(short), m_dataBlokSize, m_stream);
fclose(m_stream);
}
else
cerr <<"File "<

Bob Flynn19-Nov-04 3:53

Bob Flynn

19-Nov-04 3:53

You do not have to explicitly 0-pad the structure. It will essentialy contain garbage data or if you initialize the structure like
MyStruct data = {0};
data.b = 7;
data.b = 8; // this will result in a 0 for b because you only have
// 3 bits available

Also, b must be an unsigned int. If you need it to be signed, you will need to cast it to an int and apply sign extention rules to the unsigned value.

Henry miller19-Nov-04 6:03

Henry miller

19-Nov-04 6:03

Well you could use a union if you wanted to access the bytes seperately

union stuff {
struct {
short x;
short y;
...
}
struct {
short a :3;
short b :6;
...
}
}

(look this up in a book, it has been a long time since I've used a union so I might have something wrong here)

What I would do though is not worry the individual bytes.

struct myStruct {
short a :3;
short b :6;
}

struct myStruct data;
data.a = ...

fd = open(...);
write(fd,&data,sizeof(data));
...

which writes all the data without you having to worry about how it is stored.

rikkemus19-Nov-04 12:21

19-Nov-04 12:21

Thx for all the answers. I've learned alot.

I ended up writing a function that would feed the odd bit sizes to an array of unsigned shorts. Then i could just write them to a file later on, and extract them the reverse way.

it looked like this:

rawData = data to write to file
numberOfBits = the amount of bits from rawdata to be stored.

void ReadWriteFrame::placeBit( unsigned short rawData, unsigned short numberOfBits)
{
unsigned short Data = dataToWrite[dataPtr];
unsigned short dataBit = 0;
unsigned short bitToWrite = 0x0001;
unsigned short bitToWrite2 = 0;
unsigned short bitToRead = 0x0001;
unsigned short bitToRead2 = 0;

while(numberOfBits > 0)
{
bitToWrite2 = bitToWrite << bitPointer;

bitToRead2 = bitToRead << (numberOfBits - 1);

dataBit = rawData & bitToRead2;

if( dataBit > 0 )
dataToWrite[dataPtr] |= bitToWrite2;

numberOfBits--;
bitPointer++;
if(bitPointer > 15)
{
dataPtr++;
bitPointer = 0;
}
}
}

Thanks for the help Smile | :)

newbie needs help

marinme19-Nov-04 0:19

marinme

19-Nov-04 0:19

Hello, I'm currently trying to learn c++ and stuck on an exercise from my book. I don't have an answer guide, nor can I find the answer online.

Here is the exercise:

Design a structure called car that holds the following information about an automobile: its make as a string in a character array and the year it was built as an integer. Write a program that asks the user how many cars to catalog. The program then should use new to create a dynamic array of that many car structures. Next, it should prompt the user to input the make (which might consist of more than one word) and year information for each structure. Note that this requires some care, for it alternates reading strings with numeric data (see Chapter 4). Finally, it should display the contents of each structure. A sample run should look something like the following:

How many cars do you wish to catalog? 2
Car #1:
Please enter the make: Hudson Hornet
Please enter the year made: 1952
Car #2:
Please enter the make: Kaiser
Please enter the year made: 1951
Here is your collection:
1952 Hudson Hornet
1951 Kaiser

And here is my code:

#include <iostream>
using namespace std;

struct car
{
char make[30];
int year;
};

int main()
{
int carsToLog, i;
cout << "How many cars do you wish to catalog? ";
cin >> carsToLog;
car * pNum = new car[carsToLog];
for (i = 0;i<carstolog;i++)
{
="" cout="" <<="" endl="" "car="" #"="" i+1="" ":="" "="" endl;
="" "please="" enter="" the="" make:="" ";
="" cin.get(pnum[i]-="">make,29);
cout << endl << "Please enter the year made: ";
cin >> pNum[i]->year;

}
cout << endl << "Here is your collection: " << endl;
for(i=0;i<carstolog;i++)
cout="" <<="" pnum[i]-="">year << " " << pNum[i]->make << endl;
delete[] pNum;
return 0;
}

I am getting the following errors from VS.Net:

error C2819: type 'car' does not have an overloaded member 'operator ->'
error C2227: left of '->make' must point to class/struct/union.

When I take the array index out of the cin lines, it works, but will only access the first index of the dynamic array..

Thanks for the help in advance!

Steve S19-Nov-04 0:27

Steve S

19-Nov-04 0:27

You have a pointer named pNum. That can be used with the '->' operator, and also the indexing operator '[]'.

Either of pNum->make or pNum[0].make refer to the same object.
When you use the index operation, you don't have a pointer any more, you have an indexed instance of the thing the pointer points to.

So you can say:

pNum[i].make

or even

&pNum[i]->make

but the latter is just perverse Smile | :)

Hope this helps, and welcome to the wonderful world of C++

Steve S
Developer for hire

toxcct19-Nov-04 1:01

toxcct

19-Nov-04 1:01

Steve S wrote:
&pNum[i]->make
but the latter is just perverse

or (pNum + i)->make ?! Big Grin | :-D

TOXCCT >>> GEII power

Henry miller19-Nov-04 2:19

Henry miller

19-Nov-04 2:19

This is a student project, not the obfiscated C++ coding contest. Any student who turns in either of those two perverse options had better have a good explination as to why they did that, and not the simple pNum[i].make! Otherwise they will lose points.

I'm sure there is a good reason to use either of those forms. I can't think of one offhand though.

toxcct19-Nov-04 5:40

toxcct

19-Nov-04 5:40

yes, of course, but we're also here to share knowledges...

TOXCCT >>> GEII power

Jeryth2-Feb-05 6:14

Jeryth

2-Feb-05 6:14

Sick people WTF | :WTF:

. . . teaching pointer arithmetic to beginners. Cool | :cool:

The question "Do computers think?" is the same as "Can submarines swim?"