Windows
Some of the above values are easily available from the appropriate Win32 API, I just list them here for completeness. Others, however, need to be obtained from the Performance Data Helper library (PDH), which is a bit "unintuitive" and takes a lot of painful trial and error to get to work. (At least it took me quite a while, perhaps I've been only a bit stupid...)
Note: for clarity all error checking has been omitted from the following code. Do check the return codes...!
Total Virtual Memory:
#include "windows.h"
MEMORYSTATUSEX memInfo;
memInfo.dwLength = sizeof(MEMORYSTATUSEX);
GlobalMemoryStatusEx(&memInfo);
DWORDLONG totalVirtualMem = memInfo.ullTotalPageFile;
Note: The name "TotalPageFile" is a bit misleading here. In reality this parameter gives the "Virtual Memory Size", which is size of swap file plus installed RAM.
Virtual Memory currently used:
Same code as in "Total Virtual Memory" and then
DWORDLONG virtualMemUsed = memInfo.ullTotalPageFile - memInfo.ullAvailPageFile;
Virtual Memory currently used by current process:
#include "windows.h"
#include "psapi.h"
PROCESS_MEMORY_COUNTERS_EX pmc;
GetProcessMemoryInfo(GetCurrentProcess(), (PROCESS_MEMORY_COUNTERS*)&pmc, sizeof(pmc));
SIZE_T virtualMemUsedByMe = pmc.PrivateUsage;
Total Physical Memory (RAM):
Same code as in "Total Virtual Memory" and then
DWORDLONG totalPhysMem = memInfo.ullTotalPhys;
Physical Memory currently used:
Same code as in "Total Virtual Memory" and then
DWORDLONG physMemUsed = memInfo.ullTotalPhys - memInfo.ullAvailPhys;
Physical Memory currently used by current process:
Same code as in "Virtual Memory currently used by current process" and then
SIZE_T physMemUsedByMe = pmc.WorkingSetSize;
CPU currently used:
#include "TCHAR.h"
#include "pdh.h"
static PDH_HQUERY cpuQuery;
static PDH_HCOUNTER cpuTotal;
void init(){
PdhOpenQuery(NULL, NULL, &cpuQuery);
// You can also use L"\\Processor(*)\\% Processor Time" and get individual CPU values with PdhGetFormattedCounterArray()
PdhAddEnglishCounter(cpuQuery, L"\\Processor(_Total)\\% Processor Time", NULL, &cpuTotal);
PdhCollectQueryData(cpuQuery);
}
double getCurrentValue(){
PDH_FMT_COUNTERVALUE counterVal;
PdhCollectQueryData(cpuQuery);
PdhGetFormattedCounterValue(cpuTotal, PDH_FMT_DOUBLE, NULL, &counterVal);
return counterVal.doubleValue;
}
CPU currently used by current process:
#include "windows.h"
static ULARGE_INTEGER lastCPU, lastSysCPU, lastUserCPU;
static int numProcessors;
static HANDLE self;
void init(){
SYSTEM_INFO sysInfo;
FILETIME ftime, fsys, fuser;
GetSystemInfo(&sysInfo);
numProcessors = sysInfo.dwNumberOfProcessors;
GetSystemTimeAsFileTime(&ftime);
memcpy(&lastCPU, &ftime, sizeof(FILETIME));
self = GetCurrentProcess();
GetProcessTimes(self, &ftime, &ftime, &fsys, &fuser);
memcpy(&lastSysCPU, &fsys, sizeof(FILETIME));
memcpy(&lastUserCPU, &fuser, sizeof(FILETIME));
}
double getCurrentValue(){
FILETIME ftime, fsys, fuser;
ULARGE_INTEGER now, sys, user;
double percent;
GetSystemTimeAsFileTime(&ftime);
memcpy(&now, &ftime, sizeof(FILETIME));
GetProcessTimes(self, &ftime, &ftime, &fsys, &fuser);
memcpy(&sys, &fsys, sizeof(FILETIME));
memcpy(&user, &fuser, sizeof(FILETIME));
percent = (sys.QuadPart - lastSysCPU.QuadPart) +
(user.QuadPart - lastUserCPU.QuadPart);
percent /= (now.QuadPart - lastCPU.QuadPart);
percent /= numProcessors;
lastCPU = now;
lastUserCPU = user;
lastSysCPU = sys;
return percent * 100;
}
Linux
On Linux the choice that seemed obvious at first was to use the POSIX APIs like getrusage()
etc. I spent some time trying to get this to work, but never got meaningful values. When I finally checked the kernel sources themselves, I found out that apparently these APIs are not yet completely implemented as of Linux kernel 2.6!?
In the end I got all values via a combination of reading the pseudo-filesystem /proc
and kernel calls.
Total Virtual Memory:
#include "sys/types.h"
#include "sys/sysinfo.h"
struct sysinfo memInfo;
sysinfo (&memInfo);
long long totalVirtualMem = memInfo.totalram;
//Add other values in next statement to avoid int overflow on right hand side...
totalVirtualMem += memInfo.totalswap;
totalVirtualMem *= memInfo.mem_unit;
Virtual Memory currently used:
Same code as in "Total Virtual Memory" and then
long long virtualMemUsed = memInfo.totalram - memInfo.freeram;
//Add other values in next statement to avoid int overflow on right hand side...
virtualMemUsed += memInfo.totalswap - memInfo.freeswap;
virtualMemUsed *= memInfo.mem_unit;
Virtual Memory currently used by current process:
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
int parseLine(char* line){
// This assumes that a digit will be found and the line ends in " Kb".
int i = strlen(line);
const char* p = line;
while (*p <'0' || *p > '9') p++;
line[i-3] = '\0';
i = atoi(p);
return i;
}
int getValue(){ //Note: this value is in KB!
FILE* file = fopen("/proc/self/status", "r");
int result = -1;
char line[128];
while (fgets(line, 128, file) != NULL){
if (strncmp(line, "VmSize:", 7) == 0){
result = parseLine(line);
break;
}
}
fclose(file);
return result;
}
Total Physical Memory (RAM):
Same code as in "Total Virtual Memory" and then
long long totalPhysMem = memInfo.totalram;
//Multiply in next statement to avoid int overflow on right hand side...
totalPhysMem *= memInfo.mem_unit;
Physical Memory currently used:
Same code as in "Total Virtual Memory" and then
long long physMemUsed = memInfo.totalram - memInfo.freeram;
//Multiply in next statement to avoid int overflow on right hand side...
physMemUsed *= memInfo.mem_unit;
Physical Memory currently used by current process:
Change getValue() in "Virtual Memory currently used by current process" as follows:
int getValue(){ //Note: this value is in KB!
FILE* file = fopen("/proc/self/status", "r");
int result = -1;
char line[128];
while (fgets(line, 128, file) != NULL){
if (strncmp(line, "VmRSS:", 6) == 0){
result = parseLine(line);
break;
}
}
fclose(file);
return result;
}
CPU currently used:
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
static unsigned long long lastTotalUser, lastTotalUserLow, lastTotalSys, lastTotalIdle;
void init(){
FILE* file = fopen("/proc/stat", "r");
fscanf(file, "cpu %llu %llu %llu %llu", &lastTotalUser, &lastTotalUserLow,
&lastTotalSys, &lastTotalIdle);
fclose(file);
}
double getCurrentValue(){
double percent;
FILE* file;
unsigned long long totalUser, totalUserLow, totalSys, totalIdle, total;
file = fopen("/proc/stat", "r");
fscanf(file, "cpu %llu %llu %llu %llu", &totalUser, &totalUserLow,
&totalSys, &totalIdle);
fclose(file);
if (totalUser < lastTotalUser || totalUserLow < lastTotalUserLow ||
totalSys < lastTotalSys || totalIdle < lastTotalIdle){
//Overflow detection. Just skip this value.
percent = -1.0;
}
else{
total = (totalUser - lastTotalUser) + (totalUserLow - lastTotalUserLow) +
(totalSys - lastTotalSys);
percent = total;
total += (totalIdle - lastTotalIdle);
percent /= total;
percent *= 100;
}
lastTotalUser = totalUser;
lastTotalUserLow = totalUserLow;
lastTotalSys = totalSys;
lastTotalIdle = totalIdle;
return percent;
}
CPU currently used by current process:
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include "sys/times.h"
#include "sys/vtimes.h"
static clock_t lastCPU, lastSysCPU, lastUserCPU;
static int numProcessors;
void init(){
FILE* file;
struct tms timeSample;
char line[128];
lastCPU = times(&timeSample);
lastSysCPU = timeSample.tms_stime;
lastUserCPU = timeSample.tms_utime;
file = fopen("/proc/cpuinfo", "r");
numProcessors = 0;
while(fgets(line, 128, file) != NULL){
if (strncmp(line, "processor", 9) == 0) numProcessors++;
}
fclose(file);
}
double getCurrentValue(){
struct tms timeSample;
clock_t now;
double percent;
now = times(&timeSample);
if (now <= lastCPU || timeSample.tms_stime < lastSysCPU ||
timeSample.tms_utime < lastUserCPU){
//Overflow detection. Just skip this value.
percent = -1.0;
}
else{
percent = (timeSample.tms_stime - lastSysCPU) +
(timeSample.tms_utime - lastUserCPU);
percent /= (now - lastCPU);
percent /= numProcessors;
percent *= 100;
}
lastCPU = now;
lastSysCPU = timeSample.tms_stime;
lastUserCPU = timeSample.tms_utime;
return percent;
}
TODO: Other Platforms
I would assume, that some of the Linux code also works for the Unixes, except for the parts that read the /proc pseudo-filesystem. Perhaps on Unix these parts can be replaced by getrusage()
and similar functions?
Art of Computer Programming Volume 4: Fascicle 3 has a ton of these that might fit your particular situation better than how I describe.
Gray Codes
An issue that you will come across is of course memory and pretty quickly, you'll have problems by 20 elements in your set -- 20C3 = 1140. And if you want to iterate over the set it's best to use a modified gray code algorithm so you aren't holding all of them in memory. These generate the next combination from the previous and avoid repetitions. There are many of these for different uses. Do we want to maximize the differences between successive combinations? minimize? et cetera.
Some of the original papers describing gray codes:
- Some Hamilton Paths and a Minimal Change Algorithm
- Adjacent Interchange Combination Generation Algorithm
Here are some other papers covering the topic:
- An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm (PDF, with code in Pascal)
- Combination Generators
- Survey of Combinatorial Gray Codes (PostScript)
- An Algorithm for Gray Codes
Chase's Twiddle (algorithm)
Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects' (1970)
The algorithm in C...
Index of Combinations in Lexicographical Order (Buckles Algorithm 515)
You can also reference a combination by its index (in lexicographical order). Realizing that the index should be some amount of change from right to left based on the index we can construct something that should recover a combination.
So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change but accounts for more change since it's in the second place (proportional to the number of elements in the original set).
The method I've described is a deconstruction, as it seems, from set to the index, we need to do the reverse – which is much trickier. This is how Buckles solves the problem. I wrote some C to compute them, with minor changes – I used the index of the sets rather than a number range to represent the set, so we are always working from 0...n.
Note:
- Since combinations are unordered, {1,3,2} = {1,2,3} --we order them to be lexicographical.
- This method has an implicit 0 to start the set for the first difference.
Index of Combinations in Lexicographical Order (McCaffrey)
There is another way:, its concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it also does not produce duplicate combinations:
The set that maximizes , where .
For an example: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. So, the 27th lexicographical combination of four things is: {1,2,5,6}, those are the indexes of whatever set you want to look at. Example below (OCaml), requires choose
function, left to reader:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
A small and simple combinations iterator
The following two algorithms are provided for didactic purposes. They implement an iterator and (a more general) folder overall combinations.
They are as fast as possible, having the complexity O(nCk). The memory consumption is bound by k
.
We will start with the iterator, which will call a user provided function for each combination
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
A more general version will call the user provided function along with the state variable, starting from the initial state. Since we need to pass the state between different states we won't use the for-loop, but instead, use recursion,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
Best Answer
They probably don't want anyone to know the format to make it harder for the keygen writers.
Some ISO's have a ei.cfg file, you could check there