Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
340 lines (308 sloc) 7.58 KB
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <ctype.h>
#include <err.h>
#include <fcntl.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <fcgi_config.h>
#include <fcgi_stdio.h>
/* number of cents */
typedef unsigned price;
/* 2012-08-25 */
static const int const epoch = -734739;
/* A "fixed date" is the number of days since the epoch.
* Weekday check in |money_fare| requires epoch to be a Saturday */
typedef unsigned date;
static bool leapyear(int year) {
if (year % 4 != 0)
return 0;
switch (year % 400) {
case 100:
case 200:
case 300:
return 0;
default:
return 1;
}
}
/* Number of days since epoch for given Gregorian date */
static int fixed(int year, int month, int day) {
int yy = year - 1;
int tmp = (epoch - 1) + (365 * yy) + (yy / 4) - (yy / 100) + (yy / 400) + (((367 * month) - 362) / 12) + day;
if (month <= 2)
return tmp;
if (leapyear(year))
return tmp - 1;
else
return tmp - 2;
}
/* These values are also used by the front-end. Synchronize any changes. */
typedef enum {
zone_12_concession,
zone_12_full_fare,
zone_2_concession,
zone_2_full_fare,
NUM_FARES
} fare_type;
typedef enum {
weekend,
weekday,
weekpass,
daypass,
NUM_PRODUCTS
} ticket_type;
static price price_matrix[NUM_FARES][NUM_PRODUCTS] = {
{600, 410, 2050, 246},
{600, 820, 4100, 492},
{600, 280, 1400, 168},
{600, 560, 2800, 336},
};
enum myki {
myki_either,
myki_money,
myki_pass,
};
static const char *myki_type[] = {"EITHER", "MONEY", "PASS"};
static date *holidays;
static inline int min(int a, int b){ return (a < b) ? a : b; };
static inline int max(int a, int b){ return (a > b) ? a : b; };
/* myki money fare for a given date */
static inline price money_fare(price prices[static NUM_PRODUCTS], date d){
if ((d % 7) <= 1)
return prices[weekend];
for (date *i = holidays; *i != 0; i++)
if (d == *i)
return prices[weekend];
else if (d < *i)
break;
return prices[weekday];
}
/* myki pass fare for a given number of days */
static inline price pass_fare(price prices[static NUM_PRODUCTS], unsigned ndays) {
if (ndays <= 7)
return prices[weekpass];
else
return prices[daypass] * min(325, max(28, ndays));
}
struct node {
price cost;
unsigned ndates;
enum myki type;
};
/* best fare for a list of dates using only one of myki money or myki pass */
static price single_fare(price prices[static NUM_PRODUCTS], date * restrict dates,
unsigned ndates, enum myki * restrict best_type) {
price money = 0;
for (unsigned i = 0; i < ndates; i++)
money += money_fare(prices, *(dates+i));
price pass = pass_fare(prices, (*(dates+ndates-1) - *dates) + 1);
if (pass < money) {
*best_type = myki_pass;
return pass;
} else if (money < pass) {
*best_type = myki_money;
return money;
} else {
*best_type = myki_either;
return pass;
}
}
static void best_fare(price prices[static NUM_PRODUCTS], date * restrict dates,
unsigned ndates, struct node *cache) {
cache->ndates = ndates;
cache->cost = single_fare(prices, dates, ndates, &(cache->type));
for (unsigned i = ndates - 1; i != 0; i--) {
enum myki head_type;
price head_fare = single_fare(prices, dates, i, &head_type);
price total;
if ((cache+i)->ndates == 0)
best_fare(prices, dates+i, ndates - i, (cache+i));
total = head_fare + (cache+i)->cost;
if (total < cache->cost) {
cache->cost = total;
cache->ndates = i;
cache->type = head_type;
}
}
}
static void print36(unsigned n) {
// it takes x/log2(b) digits to show x-bit number in base b
char buf[sizeof(n) * CHAR_BIT / 5];
char *ptr = buf;
do {
unsigned a = n % 36;
*(ptr++) = (a < 10 ? '0' + a : 'a' + (a - 10));
n /= 36;
} while (n != 0);
while (ptr != buf) {
putchar(*--ptr);
}
}
static void po(struct node *n, date *dates, date offset) {
while (n->ndates != 0) {
struct node *next = n + n->ndates;
price this_cost = n->cost - next->cost;
fputs(myki_type[n->type], stdout);
putchar(':');
print36(this_cost);
putchar(':');
print36(*dates - offset);
putchar(':');
dates += n->ndates - 1;
print36(*dates - offset);
putchar('\n');
n = next;
dates++;
}
}
static inline unsigned digit36(char c) {
if ((c & 0x40) == 0)
return c - '0';
else
return (c | 0x20) - 'a' + 10;
}
static unsigned read36(char **qv) {
char *q = *qv;
unsigned n = 0;
char c = *(q++);
if (c == '\0')
exit(1); // TODO
do {
n = 36 * n + digit36(c);
} while ((c = *(q++)) != '\0' && c != ':');
*qv = q;
return n;
}
static date read_date(char **qv) {
char *q = *qv;
int c, d;
if ((c = *(q++)) == '\0' || (d = *(q++)) == '\0')
exit(1); // TODO
*qv = q;
return 36 * digit36(c) + digit36(d) - 36;
}
void p_init(void) {
date *list = holidays;
time_t tm = time(NULL);
struct tm t;
localtime_r(&tm, &t);
int t_year = t.tm_year + 1900, t_month = t.tm_mon + 1, t_day = t.tm_mday;
unsigned today = (unsigned)fixed(t_year, t_month, t_day);
t.tm_sec = 0; t.tm_min = 0; t.tm_hour = 0;
t.tm_mday += 1;
time_t tn = mktime(&t);
int diff = tn - tm;
if (diff > 600)
diff -= 600;
printf("Cache-Control: public, max-age=%d" "\r\n"
"Content-Type: text/javascript" "\r\n\r\n"
"var start_date=Date.UTC(%d, %d, %d);"
"var holidays=[", diff, t_year, t_month - 1, t_day);
bool first = 1;
date d = *list;
while (d != 0) {
if (d % 7 >= 2 && d >= today && (d - today) < 367) {
if (first)
first = 0;
else
putchar(',');
printf("%d", d - today);
}
d = *(++list);
}
putchar(']');
}
void p_fare(char *query) {
puts("Cache-Control: public, max-age=7200" "\r\n"
"Content-Type: text/json" "\r\n"
"\r");
char c = *(query++);
if (c == '\0')
exit(1); // TODO
fare_type type = c - '0';
if (type > NUM_FARES)
errx(1, "unknown fare type %d", type);
date offset = read36(&query);
unsigned ndates = read36(&query);
if (ndates > 365)
errx(1, "too many dates"); // TODO
date *dates = malloc(sizeof(date) * (ndates + 1));
*dates = 0;
for (unsigned i = 0; i < ndates; i++) {
date range_start = read_date(&query);
date range_end;
if (range_start >= 400) {
range_start -= 400;
date diff = read_date(&query);
range_end = range_start + diff;
i += diff;
} else {
range_end = range_start;
}
for (date j = range_start; j <= range_end; j++) {
date n = j + offset;
date *tmp = dates;
while (*tmp != 0 && *tmp < n)
tmp++;
while (*tmp != 0) {
date a = *tmp;
if (a == n)
errx(1, "duplicate date"); // TODO
*tmp = n;
n = a;
tmp++;
}
*tmp = n;
*(tmp+1) = 0;
if ((n - *dates) > 365)
errx(1, "too many dates"); // TODO
}
}
struct node *cache = calloc(sizeof(struct node), ndates + 1);
best_fare(price_matrix[type], dates, ndates, cache);
po(cache, dates, offset);
price money = 0;
for (unsigned i = 0; i < ndates; i++)
money += money_fare(price_matrix[type], *(dates+i));
print36(money - cache->cost);
putchar('\n');
free(cache);
free(dates);
}
int main(int argc __attribute__((unused)), const char *argv[] __attribute__((unused))) {
{
struct stat dati;
int d_f = open("hols.dat", O_RDONLY|O_NDELAY);
if (d_f != -1 && fstat(d_f, &dati) == 0) {
holidays = mmap(NULL, dati.st_size, PROT_READ, MAP_PRIVATE, d_f, 0);//leak
close(d_f);
if (holidays == MAP_FAILED) {
//holidays = malloc(sizeof(date));//leak
//*holidays = 0;
err(1, "Holidays not loaded");
}
}
}
if (setenv("TZ", ":Australia/Melbourne", 1) != 0)
err(1, "TZ");
while (FCGI_Accept() >= 0) {
char *q = getenv("QUERY_STRING");
if (q == NULL)
q = "";
if (*q == '?')
q++;
if (*q != '\0')
p_fare(q);
else
p_init();
FCGI_Finish();
}
return 0;
}
You can’t perform that action at this time.