MBound - A Memory Bound Pricing Function
Please note: MBound implementation and associated table files are provided with PennyPost solely for educational purposes to be used for learning about memory bound∞ functions. No commercial use of this algorithm is implied or suggested. To use this algorithm for any other purpose you may need permission from Microsoft.
MBound is a
memory bound∞ PricingFunction proposed by
Cynthia Dwork∞,
Andrew Goldberg∞,
Moni Naor∞.
More details about this algorithm can be found
here∞ and the complete Java implementation is
here∞.
MBound requires two
fixed-forever tables of 32-bit unsigned random integers. One of the tables is 16MB and the other 1KB. To make your implementation of memory bound compatible with
PennyPost you
will need to use the table definitions downloadable
here∞. These are released under the
LGPL∞ version 3.
Sample java code to read these files is as below:
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
/**
* This class uses longs (64 bits) instead of integers (32-bits) because JAVA
* does not support unsigned integers, so the only way to store a 32 bit
* unsigned number is inside a long. NOTE: All calculations are done assuming
* only 32 bits in the long value
*/
public final class SampleTableLoader
{
/**
* Size of T is 2^22 i.e. 16 MBytes
*/
public static final int m_iSizeOfArrayT = 0x400000;
/**
* Size of A is 256
*/
public static final int m_iSizeOfArrayA =
256;
/**
* The fixed-forever array - will be populated by populateFixedArrays() This
* array requires 16 MB and dominates the space needs of our memory-bound
* function.
*
* Keeping them static means there will be only one for all objects this is
* OK as once populated these are only to be read from and never written
* into.
*/
public static long[] m_fixedArrayT =
new long[m_iSizeOfArrayT
];
public static long[] m_fixedArrayA0 =
new long[m_iSizeOfArrayA
];
/**
* Populates T(m_fixedArrayT) and A0(m_fixedArrayA0) from files
*/
public synchronized void populateFixedArrays
() {
if (m_bFixedArraysPopulated
)
return;
// both these are loaded from the jar or classpath and located
// inside the "tab" folder within the jar or classpath
final String fileNameT =
"tab/functionT.dat";
final String fileNameA =
"tab/functionA.dat";
DataInputStream in;
in =
new DataInputStream(new BufferedInputStream(getClass
()
.
getClassLoader().
getResourceAsStream(fileNameT
)));
try {
for (int i =
0; i < m_iSizeOfArrayT; i++
) {
m_fixedArrayT
[i
] = in.
readInt() & 0xFFFFFFFFL;
}
} catch (IOException e
) {
throw new IllegalArgumentException(e
);
} finally {
try {
in.
close();
} catch (IOException e
) {
}
}
in =
new DataInputStream(new BufferedInputStream(getClass
()
.
getClassLoader().
getResourceAsStream(fileNameA
)));
try {
for (int i =
0; i < m_iSizeOfArrayA; i++
) {
m_fixedArrayA0
[i
] = in.
readInt() & 0xFFFFFFFFL;
}
} catch (IOException e
) {
//TODO: Handle this exception as appropriate
} finally {
try {
in.
close();
} catch (IOException e
) {
}
}
}
}
CategoryImplementationDocs
