/* 2.1
1. How many values can one 2-base digit take? List all of them.

0, 1

2. How many values can one 10-base digit take? List all of them.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

3. How many values can 7 bits represent? DO NOT list all of them.

2^7 = 128

4. Recall, look up or come up with a formula for a generic case: how many values can n m-valued bits represent?

m^n, where m is the base and n is the number of bits

5. If our machine is byte-addressable (i.e., each byte must have its own address), how many addresses do we need to have a table with pointers to every
 byte in 1 Megabyte?

2^20 as there are 2^20 bytes in 1 Megabyte, and each byte needs its own address

6. What if our machine was bit-addressable?

2^20 * 8 = 2^23, as each byte has 8 bits, and each bit needs its own address

7. Consider you are using an array of pointers, each entry of which is sixty-four bits (or 8 bytes) to have a pointer to each individual byte from the
 question 5, how much memory would this array occupy?

2^20 * 8 = 2^23 bytes = 8388608 bytes, as each pointer is 8 bytes, and there are 2^20 bytes in 1 Megabyte

8. Consider you are using an array of pointers, each entry of which is sixty-four bits (or 8 bytes) to have a pointer to each individual bit from the
question 6, how much memory would this array occupy?

2^23 * 8 = 2^26 bytes = 67108864 bytes, as each pointer is 8 bytes, and there are 2^23 bits in 1 Megabyte

*/

/* 2.2
1. Output of program

Read 4097
Physical address is 1, logical address is 4097
Read 100
Physical address is 4196, logical address is 100
Read 500
Physical address is 4596, logical address is 500
Read 12000
Physical address is 7904, logical address is 12000
Read 300
Physical address is 8492, logical address is 300
Read 8500
Physical address is 4404, logical address is 8500
Read 5000
Physical address is 904, logical address is 5000
Read 25300
Physical address is 8916, logical address is 25300
Read 4700
Physical address is 604, logical address is 4700
Read 13000
Physical address is 13000, logical address is 13000
Read 15000
Physical address is 15000, logical address is 15000
Read 22140
Physical address is 18044, logical address is 22140
Read 27000
Physical address is 10616, logical address is 27000

2. How many megabytes are required to store 2^20 integers?

2^20 * 4 = 2^22 bytes = 4194304 bytes = 4 megabytes, this is assuming an int is a 32-bit integer,
which may not be true on all architectures, but is on x86_64 machines.
*/


#include <stdio.h>
#include <stdlib.h>

#define OFFSETBITS 12
// fancy way of computing 2^OFFSETBITS
#define PAGESIZE (1 << OFFSETBITS)
#define WORDSIZE 32
#define FRAMESIZE (1 << (WORDSIZE - OFFSETBITS))

int getPageNumber(int logicalAddress) {
	return logicalAddress / PAGESIZE;
}

int getPageOffset(int logicalAddress) {
	return logicalAddress % PAGESIZE;
}

int getStartingAddressOfTheFrameByIndex(int indexInFramesArray) {
	return indexInFramesArray * PAGESIZE;
}

int main() {
	//disable buffering on stdout
	setbuf(stdout, NULL);

	int* frames = malloc(sizeof(int) * FRAMESIZE);
	int maxPreviouslyUsedFrame = 0;
	int logicalAddress;
	int i;
	int hasAFrameAssignedBefore = 0;
	int tempFrameIndex = 0;
	while (EOF != scanf("%d\n", &logicalAddress)) {
		printf("Read %i\n", logicalAddress);
		/* reset the value of hasAFrameAssignedBefore to 0 */
		hasAFrameAssignedBefore = 0;
		/* for all the values from 0 to maxPreviouslyUsedFrame, check if there's a page number of the current logical address in the frame array. if it is,
		mark hasAFrameAssignedBefore as 1 and store the index of the frame you just found into tempFrameIndex */
		for (i = 0; i <= maxPreviouslyUsedFrame; i++) {
			if (frames[i] == getPageNumber(logicalAddress)) {
				hasAFrameAssignedBefore = 1;
				tempFrameIndex = i;
			}
		}
		/* After looking up through all the values from 0 to maxPreviouslyUsedFrame, if the page did not have a frame assigned before, assign the page number to the frame array
		in the maxPreviously used frame position, store the max previously used frame into tempFrameIndex,  increment the value of the maxPreviously used frame */
		if(!hasAFrameAssignedBefore) {
			frames[maxPreviouslyUsedFrame] = getPageNumber(logicalAddress);
			tempFrameIndex = maxPreviouslyUsedFrame;
			maxPreviouslyUsedFrame++;
		}

		/* now that you have the physical frame index corresponding to your page stored in tempFrameIndex, get the starting address of the frame by index and
		 * add the page offset to it and voila, you have your physical address. Print it out in the format
		 * printf("Physical address is %i logical address is %i\n" ..);
		 */
		int physicalAddress = getStartingAddressOfTheFrameByIndex(tempFrameIndex) + getPageOffset(logicalAddress);
		printf("Physical address is %d, logical address is %d\n", physicalAddress, logicalAddress);
	}

	free(frames);
	return 0;
}