It is essential to pack data into as little memory space as possible. Rather tha

Question

It is essential to pack data into as little memory space as possible. Rather than store each value in an int, several values can be packed into fewer ints. For example, suppose there are 9 values to be stored and no single value will be larger than 127 (therefore each value will fit in 7 bits). Then the 9 values could be packed into 2 ints as follows:

***What I am asking***: Write two functions, one to pack values into bit fields, and another to unpack values from bit fields. You will have to allocate arrays for the packed and unpacked values (malloc), and use C bitwise operators to pack several values into ints and unpack several values from its. The following code is provided (2 test programs and a header file).

Both test programs first read a sequence of bit-field widths, with any value of 0 or negative marking the
end of the widths. Then the pack test program reads values to be put into the bit fields, calls the pack
function, and prints the resulting packed array (in hex). The unpack program reads packed array
elements (in hex, but don't type 0x), calls the unpack function, and prints the resulting array of values
(one per int).

-------------header file defs.h---------------------------------------------------------------------------------------------------------

#ifndef DEFS_H
#define DEFS_H

// a structure that contains field widths
typedef struct {
int * fieldWidths; // a pointer to an array of bit field widths (in bits)
int numWidths; // the number of elements in the array (i.e., the number of bit fields)
} sizes;

// a structure that contains an array of ints containing packed data fields
typedef struct {
int * fieldValues; // a pointer to an array of ints containing packed bit fields
int n; // the number of elements in the array
} packed;

// a structure that contains an array of ints containing individual data values (one per int)
typedef struct {
int * values; // a pointer to an array of ints containing values for bit fields (one per element)
int n; // the number of elements in the array
} unpacked;

packed pack(sizes s, unpacked un);
unpacked unpack(sizes s, packed p);

#endif

------------------test program testpack.c--------------------------------------------------------------------------------------------

#include <math.h>
#include "defs.h"
/*
* Test driver for pack.
*/
int main(){

// get the field widths
printf("Enter bit field widths: ");
sizes sizeData;
sizeData.numWidths = 0;
while (true){
int value;
scanf("%d", &value);
if (value <= 0) break;
while (value > 31){
printf("bit field width must be less than 32, try again: ");
scanf("%d", &value);
if (value == 0) break;
}
sizeData.numWidths += 1;
if (sizeData.numWidths == 1){
sizeData.fieldWidths = (int *) malloc(sizeof(int));
}
else{
sizeData.fieldWidths =
(int *) realloc(sizeData.fieldWidths,sizeData.numWidths*sizeof(int));
}
sizeData.fieldWidths[sizeData.numWidths-1] = value;
}
if (sizeData.numWidths == 0){
printf("you must enter at least one field width ");
return 1;
}

// get the field values
unpacked input;
printf("Enter %d field values: ", sizeData.numWidths);
input.values = (int *)malloc(sizeData.numWidths*sizeof(int));
for (int i=0; i<sizeData.numWidths; i+=1){
scanf("%d", &(input.values[i]));
while (input.values[i] < 0 || input.values[i] >= pow(2.0,sizeData.fieldWidths[i])){
if (input.values[i] < 0){
printf("negative values are not allowed, try again: ");
}
else{
printf("the value is too big to fit in the field, try again: ");
}
scanf("%d", &(input.values[i]));
}
}

// call the pack function to pack the values into ints
packed p = pack(sizeData,input);

// print the resulting packed array of ints
for (int i=0; i<p.n; i+=1){
printf("0x%08x ", p.fieldValues[i]);
}
printf(" ");
} // end of main function

-----------------test program testunpack.c--------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include "defs.h"
/*
* Test driver for unpack.
*/
int main(){

// get the field widths
printf("Enter bit field widths: ");
sizes sizeData;
sizeData.numWidths = 0;
int totalBits = 0;
while (true){
int value;
scanf("%d", &value);
if (value <= 0) break;
while (value > 31){
printf("bit field width must be less than 32, try again: ");
scanf("%d", &value);
if (value == 0) break;
}
totalBits += value;
sizeData.numWidths += 1;
if (sizeData.numWidths == 1){
sizeData.fieldWidths = (int *) malloc(sizeof(int));
}
else{
sizeData.fieldWidths =
(int *) realloc(sizeData.fieldWidths,sizeData.numWidths*sizeof(int));
}
sizeData.fieldWidths[sizeData.numWidths-1] = value;
}
if (sizeData.numWidths == 0){
printf("you must enter at least one field width ");
return 1;
}

// get the packed words
int totalWords = (totalBits+31)/32;
packed input;
printf("Enter %d word values (in hex): ", totalWords);
input.fieldValues = (int *)malloc(totalWords*sizeof(int));
for (int i=0; i<totalWords; i+=1){
scanf("%x", &(input.fieldValues[i]));
}

// call the unpack function to unpack the values into ints
unpacked un = unpack(sizeData,input);

// print the resulting unpacked array of ints
for (int i=0; i<un.n; i+=1){
printf("%d ", un.values[i]);
}
printf(" ");
} // end of main function

Finish the following functions:

---------------------------------unpack function---------------------------------------------------------------------

#include "defs.h"
/*
* Unpack values from bit fields.
*
* Parameters:
* s - The bit field widths.
* p - The packed values.
* * Returns - unpacked values.
*/
unpacked unpack(sizes s, packed p){

} // end of unpack function

----------------------------------pack function---------------------------------------------------------------------

#include "defs.h"
/*
* Pack values into bit fields.
*
* Parameters:
* s - The bit field widths.
* un - The unpacked values.
*
* Returns - packed values.
*/
packed pack(sizes s, unpacked un){

} // end of pack function

----------------------------------------------------------------------------------

You should make the following assumptions when writing your functions:
1. No bit field will be more than 31 bits wide (the test drivers check for this).

2. There will be at least one bit field (the test drivers check for this).

3. All values in bit-fields will be positive integers and will fit in the available bits (the test driver
checks for this). Hence each bit-field is assumed to be unsigned.

4. There is no limit on the number of bit fields. Hence all arrays must be dynamically allocated
(malloc). You will get 0 on this assignment if you impose any limit what-so-ever.

5. All the bit field widths will not be the same. They might be for some test cases, but won't for
others.

6. Some bit fields may be split across two ints. There may be test cases where no bit-field needs to
be split, but there will be cases where one or more will need to be split.
--------------------------------------------------------------------------------------------

Here's a sample of running the pack test program:
Enter bit field widths: 17 10 8 19 8 0
Enter 5 field values: 1 2 3 4 5
Output: 0x00008040 0x60001014

Here's a sample of running the unpack test program:
Enter bit field widths: 17 10 8 19 8 0
Enter 2 word values (in hex): 00008040 60001014
Output: 1 2 3 4 5

Explanation / Answer

Here are both functions. RATE if satisfied. Can you keep your word by reopening the second question( which is timedout).

#include "defs.h"

//The below #define is used to extract bits
//Usage: GETMASK(7, 3) returns value = 00000000_00000000_00000000_11111000
//Usage: GETMASK(7, 0) returns value = 00000000_00000000_00000000_11111111
#define GETMASK(lastbit, firstbit) ( (0xffffffff<<(firstbit)) & (0xffffffff>>(32-(lastbit)-1) ) )
/*
* Pack values into bit fields.
*
* Parameters:
* s - The bit field widths.
* un - The unpacked values.
*
* Returns - packed values.
*/
packed pack(sizes s, unpacked un){
packed p;

int i=0, totalWidth=0, j=0;
int shift;

//Calculate the maximum of ints required to store all values
for( i=0; i<s.numWidths; i++ )
totalWidth+=s.fieldWidths[i];
p.n = ceil( totalWidth/32.0 );
p.fieldValues = (int*)malloc( sizeof(int)*p.n );
for( i=0; i<p.n; i++)
p.fieldValues[i]=0;

shift=32;
for( i=0; i<s.numWidths; i++){
//while( shift )
shift -= s.fieldWidths[i];
if( shift < 0 ){

int upperbits = s.fieldWidths[i] + shift;
int part1 = un.values[i] & GETMASK(s.fieldWidths[i]-1, s.fieldWidths[i]-upperbits);
int part2 = un.values[i] & GETMASK(s.fieldWidths[i]-upperbits-1, 0);
p.fieldValues[j++] |= part1;
shift += 32;
p.fieldValues [j] |= (part2 << shift);
continue;
}
p.fieldValues[j] |= (un.values[i] & GETMASK(s.fieldWidths[i]-1, 0)) << shift;
}
return p;
} // end of pack function

=====================unpack function===

/*
* Unpack values from bit fields.
*
* Parameters:
* s - The bit field widths.
* p - The packed values.
* * Returns - unpacked values.
*/
unpacked unpack(sizes s, packed p){
unpacked up;
int i=0, j;
int index=0, temp;

up.n = s.numWidths;
up.values = (int*)malloc(sizeof(int) * p.n);

j=0;
index=0;
temp = p.fieldValues[0];
for( i=0; i<up.n; i++){
if ( index + s.fieldWidths[i] > 32){
int part2bits = (index+s.fieldWidths[i] - 32);
int part1bits = s.fieldWidths[i] - part2bits;
int part1 = temp >> (32-part1bits);
up.values[i] = part1 << part2bits;
temp = p.fieldValues[++j];
up.values[i] |= temp >> (32-part2bits);
temp <<= part2bits;
index =part2bits;
continue;
}
up.values[i] = temp >> (32-s.fieldWidths[i]);
temp <<= s.fieldWidths[i];
index += s.fieldWidths[i];
}
return up;
} // end of unpack function

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.