#include \"bank.h\" int numOfCustomers; // the number of customers of the bank i
ID: 3624637 • Letter: #
Question
#include "bank.h"
int numOfCustomers; // the number of customers of the bank
int numOfAccounts; // the number of accounts offered by the bank
int *available; // the amount available of each customer
int **maximum; // the maximum demand of each customer
int **allocation; // the amount currently allocated to each customer
int **need; // the remaining needs of each customer
pthread_mutex_t monitor = PTHREAD_MUTEX_INITIALIZER;
/*
Initialize the bank for a number of accounts and customers.
*/
void initBank(int avail[], int n, int m)
{
// numOfAccounts is the number of accounts offered by the bank
numOfCustomers = n;
numOfAccounts = m;
// initialize the accounts array
available = calloc(numOfAccounts, sizeof(int));
arraycpy(available, avail, numOfAccounts);
// create the array for storing the maximum demand by each customer
maximum = calloc(numOfCustomers, sizeof(int*));
allocation = calloc(numOfCustomers, sizeof(int*));
need = calloc(numOfCustomers, sizeof(int*));
}
/*
This function adds a customer to the bank system.
It records its maximum fund demand with the bank.
*/
void addBankCustomer(int customerNum, int maxDemand[])
{
maximum[customerNum] = calloc(numOfAccounts, sizeof(int));
arraycpy(maximum[customerNum], maxDemand, numOfAccounts);
allocation[customerNum] = calloc(numOfAccounts, sizeof(int));
// we start with zero allocated
need[customerNum] = calloc(numOfAccounts, sizeof(int*));
arraycpy(need[customerNum], maxDemand, numOfAccounts);
}
/*
Outputs the state of the bank; i.e., funds in each account of each customer
*/
void displayFunds(int array[])
{
printf("[");
for (int i = 0; i < numOfAccounts; i++)
printf("%3d ", array[i]);
printf("]");
}
void displayBankState()
{
printf(" %15s", "Available = ");
displayFunds(available);
printf(" %15s", "Allocation = ");
for (int i = 0; i < numOfCustomers; i++)
displayFunds(allocation[i]);
printf(" %15s", "Max = ");
for (int i = 0; i < numOfCustomers; i++)
displayFunds(maximum[i]);
printf(" %15s", "Need = ");
for (int i = 0; i < numOfCustomers; i++)
displayFunds(need[i]);
printf(" ");
}
/**
Determines whether granting a request results in leaving
the system in a safe state or not.
*/
BOOLEAN isSafeState (int customerNum, int request[])
{
return TRUE;
}
/*
Make a request for funds.
*/
BOOLEAN borrow(int customerNum, int request[])
{
BOOLEAN ret = TRUE;
if (pthread_mutex_lock(&monitor) != 0)
oops("Entering borrow", errno);
if (!isSafeState(customerNum,request)) {
//printfln("Customer # " + customerNum + " is denied.");
ret = FALSE;
}
else
// if it is safe, allocate the Funds to customer customerNum
for (int i = 0; i < numOfAccounts; i++)
{
available[i] -= request[i];
allocation[customerNum][i] += request[i];
need[customerNum][i] = maximum[customerNum][i] - allocation[customerNum][i];
}
if (pthread_mutex_unlock(&monitor) != 0)
oops("Exiting borrow", errno);
return ret;
}
/*
Deposit funds
*/
BOOLEAN payback(int customerNum, int release[])
{
if (pthread_mutex_lock(&monitor) != 0)
oops("Entering payment", errno);
BOOLEAN deny = FALSE;
for (int i = 0; (deny == FALSE) && (i < numOfAccounts); i++)
if (allocation[customerNum][i] < release[i])
deny = TRUE;
for (int i = 0; (deny == FALSE) && (i < numOfAccounts); i++)
{
available[i] += release[i];
allocation[customerNum][i] -= release[i];
need[customerNum][i] = maximum[customerNum][i] - allocation[customerNum][i];
}
// there may be some threads that can now proceed
if (pthread_mutex_unlock(&monitor) != 0)
oops("Exiting payment", errno);
return NOT(deny);
}
________________________________________________________________________________________
/**
* testSolvency.c
*
*/
#include "bank.h"
void readLine(FILE *, int[]);
void strToUpper(char **);
extern void displayFunds(int[]);
int numOfCustomers;
int numOfAccounts;
void simulateBank();
void initBankFromFile(char *);
int main(int argc, char *args[])
{
if (argc < 2)
{
printf("Usage: testSolvency <input file> ");
exit(-1);
}
// get the name of the input file
initBankFromFile(args[1]);
// run the simulation
simulateBank();
}
/*
In a loop, take input from the standard console until 'Q' or 'q' is entered.
Each input should have the following syntax:
{Q | ST | [GET | PAY] <customer number> {<account funds> ...}}
e.g. (for 3 accounts and with at least 2 customers):
ST
GET 1 3 2 1
PAY 1 1 0 1
Q
*/
void simulateBank()
{
// now loop reading requests to withdraw or deposit funds
int request[numOfAccounts];
char *inp = calloc(256, sizeof(int));
while (fgets(inp, 256, stdin) != 0)
{
if (strlen(inp) == 0)
continue;
// need a copy, since "line" will be used for tokenizing, so
// it will change until it gets NULL; we would not be able to re-use it
char *line = strdup(inp);
// get transaction type - withdraw (GET) or deposit (PAY) or ST (status)
line[strlen(line) - 1] = '';
char *trans = strsep(&line, " , ");
strToUpper(&trans); // so the case does not matter
printf(" REQUEST: %s", trans);
if (trans[0] == 'Q')
{
displayBankState();
exit(1);
}
else if (strcmp(trans, "ST") == 0)
displayBankState();
else
{
if ((strcmp(trans, "GET") != 0) && (strcmp(trans, "PAY") != 0))
{
printf(" Expected input: Q | ST | [GET | PAY] <customer number> <resource #1> <#2> <#3> ... ");
continue;
}
// get the customer number making the tranaction
int custNum = atoi(strsep(&line, " , "));
printf(" %d: ", custNum);
// get the resources involved in the transaction
for (int i = 0; i < numOfAccounts; i++)
request[i] = atoi(strsep(&line, " , "));
displayFunds(request);
// now check the transaction type
if (strcmp(trans, "GET") == 0)
{
if (borrow(custNum, request) == TRUE)
printf(" *APPROVED* ");
else
printf(" *DENIED* ");
}
else if (strcmp(trans, "PAY") == 0)
if (payback(custNum, request) == TRUE)
printf(" *APPROVED* ");
else
printf(" *DENIED* ");
}
}
}
/*
Read the state of the bank from a file.
The file format is as follows:
<num of customers> <num of accounts>
<initial state of accounts>
<max needs for each customer>
e.g.,
5 3
15 10 5
7,5,3
3,2,2
9,0,2
2,2,2
4,3,3
Any of ", " is a valid separator
*/
void initBankFromFile(char *inputFile)
{
FILE *file = fopen(inputFile, "r");
if (file == 0)
{
printf("Cannot open file %s for reading. ", inputFile);
exit(-1);
}
// now get the customers and accounts
int in[2];
readLine(file, in);
numOfCustomers = in[0];
numOfAccounts = in[1];
// the initial state of the accounts
int accountState[numOfAccounts];
readLine(file, accountState);
// create the bank
initBank(accountState, numOfCustomers, numOfAccounts);
int *maxDemand[numOfCustomers];
// read initial values for maximum array
int i;
for (i = 0; i < numOfCustomers; i++)
{
maxDemand[i] = calloc(numOfAccounts, sizeof(int));
readLine(file, maxDemand[i]);
addBankCustomer(i, maxDemand[i]);
}
}
/*
Read a line of values separated by a set of delimeters from a file into an array
*/
void readLine(FILE *file, int array[])
{
char *line = calloc(256, sizeof(int));
fgets(line, 256, file);
char *tok;
int i = 0;
while ((tok = strsep(&line, ", ")) != NULL)
if (strlen(tok) > 0)
array[i++] = atoi(tok);
}
/*
Transcode the string to upper case
*/
void strToUpper(char **s)
{
char *c;
for(c = *s; *c ; c++)
if (isascii(*c) && islower(*c))
*c = toupper(*c);
}
____________________________________________________________________________________
/*
* bank.h
*
*/
#ifndef _BANK_H_
#define _BANK_H_
#include <stdio.h>
#include <stdlib.h>
#define __USE_BSD
#include <string.h>
#include <errno.h>
#define __USE_SVID
#include <ctype.h>
#include <pthread.h>
//extern char *strdup (const char *s);
//extern char *strsep(char **stringp, const char *delim);
//extern int isascii(int c);
#define MAX_NUM_OF_CUSTOMERS 32
#define MAX_NUM_OF_ACCOUNT_TYPES 32
typedef int BOOLEAN;
#define TRUE 1
#define FALSE 0
#define NOT(x) (x == TRUE ? FALSE : TRUE)
#define oops(errmsg, errnum) { perror(errmsg); exit(errnum); }
#define arraycpy(a, b, n) {int i; for (i = 0; i < n; i++) a[i] = b[i];}
void initBank(int[], int, int);
void addBankCustomer(int, int[]);
void displayBankState();
BOOLEAN borrow(int, int[]);
BOOLEAN payback(int, int[]);
#endif
Explanation / Answer
Introduction Basically, this article describes one way to implement the 1D version of the FFT algorithm for an array of complex samples. The intention of this article is to show an efficient and fast FFT algorithm that can easily be modified according to the needs of the user. I've studied the FFT algorithm when I was developing a software to make frequency analysis on a sample of captured sound. Background First of all, 95% of this code wasn't written by me. This is practically the code that is described in the book Numerical Recipes In C of 1982!!! Yes, more than 20 years ago!!! But still, in my opinion, very, very good. But this code is slightly different from the original one. When I was studying the algorithm, I had noticed a pattern that could be exploited, and based on that, I've managed to improve the algorithm with a small change in the code, and the O() (The Big O) (unit measure to the complexity of the algorithm) is reduced in N computations. (After implementing the improved method successfully, I made some research in the web and realized I discovered nothing new. I've just noticed something that someone had already seen :-P) I will not get "deep in theory", so I strongly advise the reading of chapter 12 if you want to understand "The Why". Other forms of the FFT like the 2D or the 3D FFT can be found on the book too. The FFT The Fast Fourier Transform is an optimized computational algorithm to implement the Discreet Fourier Transform to an array of 2^N samples. It allows to determine the frequency of a discreet signal, represent the signal in the frequency domain, convolution, etc... This algorithm has a complexity of O(N*log2(N)). Actually, the complexity of the algorithm is a little higher because the data needs to be prepared by an operation called bit-reversal. This bit-reversal section is presented in the Numerical Recipes In C as a O(2N) complexity. With a small change I've made to the code presented here, it makes it in O(N). This represents something like an 8% improvement of performance. Example of a signal in the frequency domain. The FFT is calculated in two parts. The first one transforms the original data array into a bit-reverse order array by applying the bit-reversal method. This makes the mathematical calculations of the second part "much more easy". The second part processes the FFT in N*log2(N) operations (application of the Danielson-Lanzcos algorithm). Let's start with an array of complex data. This array could be, for example, in this case, an array of floats in witch the data[even_index] is the real part and the data[odd_index] is the complex part. (This can be adapted to an array of real data, just by filling the complex values with 0s, or use the real array FFT implemented on the book.) The size of the array must be in an N^2 order (2, 4, 8, 16, 32, 64, etc...). In case the sample doesn't match that size, just put it in an array with the next 2^N size and fill the remaining spaces with 0s. Just a small and not very significant consideration: the original code uses data arrays considering the beginning of the information is in index 1 -> data[1], and data[0] is ignored. My code modifies that to start from 0 -> data[0]. First, we define the FFT function: Collapse //data -> float array that represent the array of complex samples //number_of_complex_samples -> number of samples (N^2 order number) //isign -> 1 to calculate FFT and -1 to calculate Reverse FFT float FFT (float data[], unsigned long number_of_complex_samples, int isign) { //variables for trigonometric recurrences unsigned long n,mmax,m,j,istep,i; double wtemp,wr,wpr,wpi,wi,theta,tempr,tempi; The Bit-Reversal Method First, the original array must be transformed in order to perform the Danielson-Lanzcos algorithm. For example, the complex[index] will swap places with the complex[bit-reverse-order-index]. If the index (in binary) is 0b00001, the bit-reverse-order-index will be 0b10000. In figure 1, you can see what happens to the data array after the transformation. The implementation of this method according to Numerical Recipes In C goes like this: Collapse //the complex array is real+complex so the array //as a size n = 2* number of complex samples // real part is the data[index] and the complex part is the data[index+1] n=number_of_complex_samples * 2; //binary inversion (note that //the indexes start from 1 witch means that the //real part of the complex is on the odd-indexes //and the complex part is on the even-indexes j=1; for (i=1;i i) { //swap the real part SWAP(data[j],data[i]); //swap the complex part SWAP(data[j+1],data[i+1]); } m=n/2; while (m >= 2 && j > m) { j -= m; m = m/2; } j += m; } The SWAP goes outside the function and it's something like this: Collapse #defineSWAP(a,b)tempr=(a);(a)=(b);(b)=tempr //tempr is a variable from our FFT function Figure 1 (8-length data array) If you pay attention at figure 1, you can see a pattern. Let's see: divide the array in half with a mirror. If you look at the reflecting side of the mirror, you will see exactly the same thing of what's in the other side. This mirrored effect allows you to do the bit-reversal method in the first half of the array and use it almost directly in the second half. But you must be careful with one thing. You can only apply this effect if the change happens in the first half only. This means that if the change is between an index of the first half and an index from the second, this is not valid, otherwise you would be making the swap and then undoing it again (do this on a 16 length data array and you will understand what I'm saying). So the code becomes something like this: Collapse //the complex array is real+complex so the array //as a size n = 2* number of complex samples // real part is the data[index] and //the complex part is the data[index+1] n=number_of_complex_samples * 2; //binary inversion (note that the indexes //start from 0 witch means that the //real part of the complex is on the even-indexes //and the complex part is on the odd-indexes j=0; for (i=0;i i) { //swap the real part SWAP(data[j],data[i]); //swap the complex part SWAP(data[j+1],data[i+1]); // checks if the changes occurs in the first half // and use the mirrored effect on the second half if((j/2)= 2 && j >= m) { j -= m; m = m/2; } j += m; } The Danielson-Lanzcos The second half of the code goes exactly like it is described in the book. This applies the N*log2(N) trigonometric recurrences to the data. The code I will show here is my version (data starts at index 0): Collapse //Danielson-Lanzcos routine mmax=2; //external loop while (n > mmax) { istep = mmaxRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.