rand-test.c

#define PLAYLIST_ITEMS (50)

#define RAND_WINDOWS (1)
#define RAND_FREEBSD (2)
#define USE_RAND RAND_WINDOWS

#define BIG_PLAYLIST (PLAYLIST_ITEMS > 50)

#define _CRT_RAND_S
#define __USE_MINGW_ANSI_STDIO
#include <stdlib.h>
#include <stdio.h>

#define MPSWAP(type, a, b) \
	do { type SWAP_tmp = b; b = a; a = SWAP_tmp; } while (0)
#define MPMIN(a, b) ((a) > (b) ? (b) : (a))

static unsigned int get_seed(void)
{
	unsigned val;
	rand_s(&val);

	// mpv calls srand() with the value of the monotonic clock (or OS-specific
	// equivalent) in microseconds. The monotonic clock is probably based on the
	// computer's uptime. Let's assume the user always starts mpv about 10±5
	// minutes after boot.
	return 600000000 + (val >> 4);
}

#if USE_RAND == RAND_WINDOWS

#define TEST_RAND_MAX (0x7fff)
static unsigned int test_state = 1;
static void test_srand(unsigned seed)
{
	test_state = seed;
}
static int test_rand(void)
{
	test_state = test_state * 214013 + 2531011;
	return (test_state >> 16) & TEST_RAND_MAX;
}

#elif USE_RAND == RAND_FREEBSD

#define TEST_RAND_MAX (0x7ffffffd)
static unsigned int test_state = 1;
static void test_srand(unsigned seed)
{
	test_state = seed;
}
static int test_rand(void)
{
	long hi, lo, x;

	/* Transform to [1, 0x7ffffffe] range. */
	x = (test_state % 0x7ffffffe) + 1;
	hi = x / 127773;
	lo = x % 127773;
	x = 16807 * lo - 2836 * hi;
	if (x < 0)
		x += 0x7fffffff;
	/* Transform to [0, 0x7ffffffd] range. */
	x--;
	test_state = x;
	return (x);
}

#endif

struct playlist_stats {
	unsigned long long position_count[PLAYLIST_ITEMS];
#if !BIG_PLAYLIST
	unsigned long long next_count[PLAYLIST_ITEMS][PLAYLIST_ITEMS];
#endif
};

int main()
{
	int *playlist = calloc(PLAYLIST_ITEMS, sizeof *playlist);
	struct playlist_stats *stats = calloc(PLAYLIST_ITEMS, sizeof *stats);

	for (int i = 0; i < 10000000; i++) {
		test_srand(get_seed());

		// Initialize the "playlist"
		for (int j = 0; j < PLAYLIST_ITEMS; j++)
			playlist[j] = j;

		// Shuffle the playlist using the same algorithm as mpv
		for (int n = 0; n < PLAYLIST_ITEMS - 1; n++) {
			int j = (int)((double)(PLAYLIST_ITEMS - n) * test_rand() / (TEST_RAND_MAX + 1.0));
			MPSWAP(int, playlist[n], playlist[n + j]);
		}

		for (int j = 0; j < PLAYLIST_ITEMS; j++) {
			stats[playlist[j]].position_count[j]++;
#if !BIG_PLAYLIST
			for (int n = 1; n < 5; n++) {
				if (j < PLAYLIST_ITEMS - n)
					stats[playlist[j]].next_count[n][playlist[j + n]]++;
			}
#endif
		}
	}

	printf("Most likely playlist position:\n");

	printf("           ");
#if !BIG_PLAYLIST
	for (int i = 0; i < PLAYLIST_ITEMS; i++)
		printf("%7d", i + 1);
#endif
	printf("\n");

	int max_val = 0;
	for (int i = 0; i < PLAYLIST_ITEMS; i++) {
		for (int j = 0; j < PLAYLIST_ITEMS; j++) {
			if (max_val < stats[i].position_count[j])
				max_val = stats[i].position_count[j];
		}
	}

	for (int i = 0; i < MPMIN(PLAYLIST_ITEMS, 50); i++) {
		printf("Track %3d: ", i + 1);
		for (int j = 0; j < MPMIN(PLAYLIST_ITEMS, 350); j++) {
			printf("\e[1;%d;48;2;0;%llu;0m",
			       stats[i].position_count[j] > max_val / 2 ? 30 : 37,
			       stats[i].position_count[j] * 255 / max_val);
#if BIG_PLAYLIST
			printf(" ");
#else
			printf("%7llu", stats[i].position_count[j]);
#endif
		}
		printf("\e[0m\n");
	}

#if !BIG_PLAYLIST
	for (int n = 1; n < 5; n++) {
		printf("\n");

		printf("Most likely n+%d track:\n", n);
		printf("           ");
		for (int i = 0; i < PLAYLIST_ITEMS; i++)
			printf("%7d", i + 1);
		printf("\n");

		max_val = 0;
		for (int i = 0; i < PLAYLIST_ITEMS; i++) {
			for (int j = 0; j < PLAYLIST_ITEMS; j++) {
				if (max_val < stats[i].next_count[n][j])
					max_val = stats[i].next_count[n][j];
			}
		}

		for (int i = 0; i < PLAYLIST_ITEMS; i++) {
			printf("Track %3d: ", i + 1);
			for (int j = 0; j < PLAYLIST_ITEMS; j++) {
				printf("\e[1;%d;48;2;0;%llu;0m",
				       stats[i].next_count[n][j] > max_val / 2 ? 30 : 37,
				       stats[i].next_count[n][j] * 255 / max_val);
				printf("%7llu", stats[i].next_count[n][j]);
			}
			printf("\e[0m\n");
		}
	}
#endif
}