//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "HW #7B"
#define REVISION   (0)
#define TITLE      "Large Dynamically Allocated Arrays"
#define SUBTITLE   "Extra Credit"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "07b0soln.c"
//=========================================================================

// PROBLEM:
//
// The largest amount of memory that malloc() can allocate is one byte
// less than 64KBytes - or (2^16 - 1) - which is 65535 bytes of memory.
//
// How restrictive is this limitation? What is the largest image you
// could work with if the image is a 24-bit color image in a 4:3 format?
//
// What if you need to work with a data set, such as an image, that
// needs more than this. Describe a scheme for using multiple calls to
// malloc() such that you can store all of a much larger image. How do
// you allocate the memory and how do you map a given pixel to a location
// within one of these multiple blocks?

// SOLUTION:
//
// Method 1: Create a virtual 1D array that is arbitratily large.
//
// 1) How much memory is needed?
//
//    bytes = biWidth * biHeight * BytesPerPixel   (24bit => 3 bytes/pixel)
//
// 2) Allocate N full size blocks where each block is FULLSIZE large.
//    Store the pointers to these blocks in an array of pointers.
//
//    image is a pointer to an array of pointers, which is the same thing
//    as declaring image to be:
//
//    unsigned char **image
//
//    N_full = (bytes/FULLSIZE) + 1  (integer division)
//    N_part = (bytes%FULLSIZE > 0)  (0 ot 1 fractional block needed)
//
//    image = malloc((N_full+N_part)*sizeof(unsigned char *))
//
//    for(i = 0; i < N_full; i++)      // allocate the full size blocks
//       image[i] = malloc(FULLSIZE)
//
//    if(N_part)                       // allocate any part size block
//       image[N_full] = malloc(bytes%FULLSIZE)
//
// 3) Map data to memory location
//
//    Location is a virtual 1D array:
//
//    offset = row*(BytesPerPixel*cols) + col*BytesPerPixel + color
//
//       where color = 0, 1, or 2 for blue, green, and red respectively
//
//    No use the same approach as above to determine the block and offset
//
//    block_no  = (offset/FULLSIZE)  (integer division)
//    block_off = (offset%FULLSIZE)
//
//    The data element is then:
//
//    image[block_no][block_off]
//
// Method 2: Create a virtual 2D array that matches the image layout.
//
// Notice that our final syntax is in a 2D format and that matches the
// logical layout of our data - we rows and columns of pixels. So if we
// select the FULLSIZE parameter just right, we should be able to simplify
// our computations.
//
// 1) Determine the size of a full-size block
//
// Since FULLSIZE is the amount of data in one block, and since the number
// of the block is the first index to the image[][] array above, we would
// like this to map to a single row of data. So we will calculate the
// size of a full block instead of hard coding it.
//
//     fullsize = biWidth*BytesPerPixel    // bytes on a single row.
//
// Notice that there will be no part size blocks.
//
// It's also important to note that fullsize still can't exceed 65,535
// otherwise we have problems. This means that the maximum width of a
// 24-bit image that we can use this stratagy with is 21845 pixels wide
// This is not a serious limitation.
//
// 2) Allocate memory - very similar to the above except leveraging what
// we know about the the relationship between the number of blocks and the
// number of rows in the image.
//
//    unsigned char **image
//
//    image = malloc((biHeight)*sizeof(unsigned char *))
//
//    for(i = 0; i < bi_Height; i++)      // allocate the full size blocks
//       image[i] = malloc(fullsize)
//
// 3) Map data to memory location
//
//    Location is a virtual 2D array:
//
//    The row in the image array is simply the row in the image.
//    But there are still three bytes per column so we still have to
//    take that into account.
//
//    The data element is then:
//
//    image[row][col*BytesPerPixel + color]
//
//       where color = 0, 1, or 2 for blue, green, and red respectively
//
// Method 3: Create a virtual 3D array
//
// It might seem nice to take this one step further and use a 3D array.
// This would permit use to use the following mapping:
//
//    image[row][col][color]
//
// which would certainly be convenient.
//
// We can do this, but it requires an additional level of indirection
// which, in this case, means that instead of (biHeight) row pointers,
// we need (biHeight*biWidth) color pointers and we run right back into
// the same problem that we did before except now it is because the number
// of pointers we need exceeds 65,535 except for small images.
//
// This can be overcome by some clever programming in order to hide the
// details of getting around this complication, but it isn't worth it.
//
// We can get a very similar feel by using the following syntax:
//
//    image[row][ColOffset(col, color)]
//
// where ColOffset() is a function or macro such as:
//
// #define BYTESPERPIXEL (3)
// #define ColOffset(col, color) (BYTESPERPIXEL*(col) + (color))