Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
constexpr Brainfuck compiler (x86)
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <iostream>
#include <fstream>
#include <sprout/config.hpp>
#include <sprout/endian_traits.hpp>
#include <sprout/string.hpp>
#include <sprout/array.hpp>
#include <sprout/sub_array.hpp>
#include <sprout/container/functions.hpp>
#include <sprout/range/algorithm.hpp>
#include <sprout/preprocessor/stringize.hpp>
#include <sprout/assert.hpp>
//
// PE関連の構造体
// <windows.h> からコピペ
//
typedef unsigned long DWORD;
typedef int BOOL;
typedef unsigned char BYTE;
typedef unsigned short WORD;
//
// File header format.
//
typedef struct _IMAGE_FILE_HEADER {
WORD Machine;
WORD NumberOfSections;
DWORD TimeDateStamp;
DWORD PointerToSymbolTable;
DWORD NumberOfSymbols;
WORD SizeOfOptionalHeader;
WORD Characteristics;
} IMAGE_FILE_HEADER, *PIMAGE_FILE_HEADER;
//
// Directory format.
//
typedef struct _IMAGE_DATA_DIRECTORY {
DWORD VirtualAddress;
DWORD Size;
} IMAGE_DATA_DIRECTORY, *PIMAGE_DATA_DIRECTORY;
#define IMAGE_NUMBEROF_DIRECTORY_ENTRIES 16
//
// Optional header format.
//
typedef struct _IMAGE_OPTIONAL_HEADER {
//
// Standard fields.
//
WORD Magic;
BYTE MajorLinkerVersion;
BYTE MinorLinkerVersion;
DWORD SizeOfCode;
DWORD SizeOfInitializedData;
DWORD SizeOfUninitializedData;
DWORD AddressOfEntryPoint;
DWORD BaseOfCode;
DWORD BaseOfData;
//
// NT additional fields.
//
DWORD ImageBase;
DWORD SectionAlignment;
DWORD FileAlignment;
WORD MajorOperatingSystemVersion;
WORD MinorOperatingSystemVersion;
WORD MajorImageVersion;
WORD MinorImageVersion;
WORD MajorSubsystemVersion;
WORD MinorSubsystemVersion;
DWORD Win32VersionValue;
DWORD SizeOfImage;
DWORD SizeOfHeaders;
DWORD CheckSum;
WORD Subsystem;
WORD DllCharacteristics;
DWORD SizeOfStackReserve;
DWORD SizeOfStackCommit;
DWORD SizeOfHeapReserve;
DWORD SizeOfHeapCommit;
DWORD LoaderFlags;
DWORD NumberOfRvaAndSizes;
IMAGE_DATA_DIRECTORY DataDirectory[IMAGE_NUMBEROF_DIRECTORY_ENTRIES];
} IMAGE_OPTIONAL_HEADER32, *PIMAGE_OPTIONAL_HEADER32;
//
// Section header format.
//
#define IMAGE_SIZEOF_SHORT_NAME 8
typedef struct _IMAGE_SECTION_HEADER {
BYTE Name[IMAGE_SIZEOF_SHORT_NAME];
// union {
// DWORD PhysicalAddress;
// DWORD VirtualSize;
// } Misc;
struct {
DWORD VirtualSize;
} Misc;
DWORD VirtualAddress;
DWORD SizeOfRawData;
DWORD PointerToRawData;
DWORD PointerToRelocations;
DWORD PointerToLinenumbers;
WORD NumberOfRelocations;
WORD NumberOfLinenumbers;
DWORD Characteristics;
} IMAGE_SECTION_HEADER, *PIMAGE_SECTION_HEADER;
//
// 出力バイナリサイズ
//
#ifndef BRAINFUCK_BINARY_SIZE
# define BRAINFUCK_BINARY_SIZE (16 * 1024)
#endif
//
// ループ制限
//
#ifndef BRAINFUCK_LOOP_LIMIT
# define BRAINFUCK_LOOP_LIMIT 256
#endif
//
// 入力ファイル名
//
#ifndef BRAINFUCK_SOURCE_FILE
# define BRAINFUCK_SOURCE_FILE a.bf
#endif
//
// 定数
//
SPROUT_STATIC_CONSTEXPR std::size_t bin_size = BRAINFUCK_BINARY_SIZE;
SPROUT_STATIC_CONSTEXPR std::size_t loop_limit = BRAINFUCK_LOOP_LIMIT;
SPROUT_STATIC_CONSTEXPR auto source = sprout::to_string(
# include SPROUT_PP_STRINGIZE(BRAINFUCK_SOURCE_FILE)
);
SPROUT_STATIC_CONSTEXPR std::int32_t addr_putchar = 0x00405044;
SPROUT_STATIC_CONSTEXPR std::int32_t addr_getchar = addr_putchar + 4;
SPROUT_STATIC_CONSTEXPR std::int32_t addr_buf = 0x00406000;
//
// 出力用関数
//
template<typename OutputIterator, typename T>
SPROUT_CXX14_CONSTEXPR std::size_t
write_bytes(OutputIterator& out, T const& val) {
typedef sprout::little_endian_traits<T> traits;
for (std::size_t i = 0; i != traits::size(); ++i) {
*out++ = sprout::little_endian_traits<T>::get_byte(val, i);
}
return traits::size();
}
template<typename OutputIterator, typename T, std::size_t N>
SPROUT_CXX14_CONSTEXPR std::size_t
write_bytes(OutputIterator& out, T const(& vals)[N]) {
typedef sprout::little_endian_traits<T> traits;
for (std::size_t i = 0; i != N; ++i) {
::write_bytes(out, vals[i]);
}
return traits::size() * N;
}
template<typename OutputIterator, typename Head, typename... Tail>
SPROUT_CXX14_CONSTEXPR std::size_t
write_bytes(OutputIterator& out, Head const& head, Tail const&... tail) {
return ::write_bytes(out, head) + ::write_bytes(out, tail...);
}
template<typename OutputIterator>
SPROUT_CXX14_CONSTEXPR std::size_t
write_pe_header(OutputIterator& out, std::size_t n = 0) {
SPROUT_CONSTEXPR unsigned char stub[] = {
// 00-3b: DOS Header
'M', 'Z', 0x50, 0x00, 0x02, 0x00, 0x00, 0x00, 0x04, 0x00, 0x0f, 0x00, 0xff, 0xff, 0x00, 0x00,
0xb8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x1a, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
// 3c-3f: Pointer to PE Header (=80)
0x80, 0x00, 0x00, 0x00,
// 40-7f: DOS Stub
0xba, 0x10, 0x00, 0x0e, 0x1f, 0xb4, 0x09, 0xcd, 0x21, 0xb8, 0x01, 0x4c, 0xcd, 0x21, 0x90, 0x90,
'T', 'h', 'i', 's', ' ', 'p', 'r', 'o', 'g', 'r', 'a', 'm', ' ', 'c', 'a', 'n',
'n', 'o', 't', ' ', 'b', 'e', ' ', 'r', 'u', 'n', ' ', 'i', 'n', ' ', 'D', 'O',
'S', ' ', 'm', 'o', 'd', 'e', '.', '\r', '\n', '$', 0, 0, 0, 0, 0, 0,
// 80-83: PE Signature
'P', 'E', 0, 0
};
n += ::write_bytes(
out,
stub
);
SPROUT_CONSTEXPR ::IMAGE_FILE_HEADER coff = {
0x014c, // Machine
3, // NumberOfSections
0, // TimeDateStamp
0, // PointerToSymbolTable
0, // NumberOfSymbols
sizeof(::IMAGE_OPTIONAL_HEADER32), // SizeOfOptionalHeader
0x030f // Characteristics
};
n += ::write_bytes(
out,
coff.Machine,
coff.NumberOfSections,
coff.TimeDateStamp,
coff.PointerToSymbolTable,
coff.NumberOfSymbols,
coff.SizeOfOptionalHeader,
coff.Characteristics
);
SPROUT_CONSTEXPR ::IMAGE_OPTIONAL_HEADER32 opt = {
0x010b, // Magic
6, 0, // MajorLinkerVersion, MinorLinkerVersion
::bin_size, // SizeOfCode
0, // SizeOfInitializedData
65536, // SizeOfUninitializedData
0x1000, // AddressOfEntryPoint
0x1000, // BaseOfCode
0x6000, // BaseOfData
0x00400000, // ImageBase
0x1000, // SectionAlignment
0x0200, // FileAlignment
4, 0, // MajorOperatingSystemVersion, MinorOperatingSystemVersion
0, 0, // MajorImageVersion, MinorImageVersion
4, 0, // MajorSubsystemVersion, MinorSubsystemVersion
0, // Win32VersionValue
0x16000, // SizeOfImage
0x200, // SizeOfHeaders
0, // CheckSum
3, // Subsystem
0, // DllCharacteristics
1024 * 1024, // SizeOfStackReserve
8 * 1024, // SizeOfStackCommit
1024 * 1024, // SizeOfHeapReserve
4 * 1024, // SizeOfHeapCommit
0, // LoaderFlags
16, // NumberOfRvaAndSizes
{
{},
{
0x5000, // VirtualAddress (import table)
100 // Size
},
{}
}
};
n += ::write_bytes(
out,
opt.Magic,
opt.MajorLinkerVersion, opt.MinorLinkerVersion,
opt.SizeOfCode,
opt.SizeOfInitializedData,
opt.SizeOfUninitializedData,
opt.AddressOfEntryPoint,
opt.BaseOfCode,
opt.BaseOfData,
opt.ImageBase,
opt.SectionAlignment,
opt.FileAlignment,
opt.MajorOperatingSystemVersion, opt.MinorOperatingSystemVersion,
opt.MajorImageVersion, opt.MinorImageVersion,
opt.MajorSubsystemVersion, opt.MinorSubsystemVersion,
opt.Win32VersionValue,
opt.SizeOfImage,
opt.SizeOfHeaders,
opt.CheckSum,
opt.Subsystem,
opt.DllCharacteristics,
opt.SizeOfStackReserve,
opt.SizeOfStackCommit,
opt.SizeOfHeapReserve,
opt.SizeOfHeapCommit,
opt.LoaderFlags,
opt.NumberOfRvaAndSizes,
opt.DataDirectory[0].VirtualAddress, opt.DataDirectory[0].Size,
opt.DataDirectory[1].VirtualAddress, opt.DataDirectory[1].Size
);
for (std::size_t i = 2; i != IMAGE_NUMBEROF_DIRECTORY_ENTRIES; ++i) {
n += ::write_bytes(
out,
opt.DataDirectory[i].VirtualAddress, opt.DataDirectory[i].Size
);
}
SPROUT_CONSTEXPR ::IMAGE_SECTION_HEADER sects[3] = {
{
".text", // Name
{::bin_size}, // Misc.VirtualSize
0x1000, // VirtualAddress
::bin_size, // SizeOfRawData
0x400, // PointerToRawData
0, // PointerToRelocations
0, // PointerToLinenumbers
0, // NumberOfRelocations
0, // NumberOfLinenumbers
0x60500060 // Characteristics
},
{
".idata", // Name
{100}, // Misc.VirtualSize
0x5000, // VirtualAddress
512, // SizeOfRawData
0x200, // PointerToRawData
0, // PointerToRelocations
0, // PointerToLinenumbers
0, // NumberOfRelocations
0, // NumberOfLinenumbers
0xc0300040 // Characteristics
},
{
".bss", // Name
{65536}, // Misc.VirtualSize
0x6000, // VirtualAddress
0, // SizeOfRawData
0, // PointerToRawData
0, // PointerToRelocations
0, // PointerToLinenumbers
0, // NumberOfRelocations
0, // NumberOfLinenumbers
0xc0400080 // Characteristics
}
};
for (std::size_t i = 0; i != 3; ++i) {
n += ::write_bytes(
out,
sects[i].Name,
sects[i].Misc.VirtualSize,
sects[i].VirtualAddress,
sects[i].SizeOfRawData,
sects[i].PointerToRawData,
sects[i].PointerToRelocations,
sects[i].PointerToLinenumbers,
sects[i].NumberOfRelocations,
sects[i].NumberOfLinenumbers,
sects[i].Characteristics
);
}
for (; n != 0x200; ) {
n += ::write_bytes(
out,
(unsigned char)0
);
}
return n;
}
template<typename OutputIterator>
SPROUT_CXX14_CONSTEXPR std::size_t
write_idata(OutputIterator& out, std::size_t n = 0) {
SPROUT_CONSTEXPR int idt[] = {
// IDT 1
0x5028, 0, 0, 0x5034, 0x5044,
// IDT (終端)
0, 0, 0, 0, 0
};
n += ::write_bytes(
out,
idt
);
SPROUT_CONSTEXPR int ilt_iat[] = {
0x5050, 0x505a, 0
};
// ILT
n += ::write_bytes(
out,
ilt_iat
);
n += ::write_bytes(
out,
"msvcrt.dll\0\0\0\0\0"
);
// IAT
n += ::write_bytes(
out,
ilt_iat
);
n += ::write_bytes(
out,
(std::int16_t)0,
"putchar",
(std::int16_t)0,
"getchar"
);
for (; n != 0x400; ) {
n += ::write_bytes(
out,
(unsigned char)0
);
}
return n;
}
//
// コンパイル
//
template<std::size_t LoopLimit = 256, typename InputIterator, typename RandomAccessIterator>
SPROUT_CXX14_CONSTEXPR std::size_t
compile(InputIterator first, InputIterator last, RandomAccessIterator& out_first) {
sprout::array<int, LoopLimit> loops {{}}; // ループを保存するスタック
auto loop_first = sprout::begin(loops);
auto loop_last = sprout::end(loops);
auto loop = loop_first;
int idx = 0;
auto out = out_first;
idx += ::write_bytes(
out,
(unsigned char)0x31, (unsigned char)0xc9, // xor ecx, ecx
(unsigned char)0x57, // push edi
(unsigned char)0xbf, ::addr_buf // mov edi, addr_buf
);
for (; first != last; ++first) {
switch (*first) {
case '>':
idx += ::write_bytes(
out,
(unsigned char)0x66, (unsigned char)0x41 // inc cx
);
break;
case '<':
idx += ::write_bytes(
out,
(unsigned char)0x66, (unsigned char)0x49 // dec cx
);
break;
case '+':
idx += ::write_bytes(
out,
(unsigned char)0xfe, (unsigned char)0x04, (unsigned char)0x0f // inc byte [edi+ecx]
);
break;
case '-':
idx += ::write_bytes(
out,
(unsigned char)0xfe, (unsigned char)0x0c, (unsigned char)0x0f // dec byte [edi+ecx]
);
break;
case '.':
idx += ::write_bytes(
out,
(unsigned char)0x51, // push ecx
(unsigned char)0x0f, (unsigned char)0xb6, (unsigned char)0x04, (unsigned char)0x0f, // movzx eax,byte [edi+ecx]
(unsigned char)0x50, // push eax
(unsigned char)0xa1, ::addr_putchar, // mov eax, [addr_putchar]
(unsigned char)0xff, (unsigned char)0xd0, // call eax
(unsigned char)0x58, // pop eax
(unsigned char)0x59 // pop ecx
);
break;
case ',':
idx += ::write_bytes(
out,
(unsigned char)0x51, // push ecx
(unsigned char)0xa1, ::addr_getchar, // mov eax, [addr_getchar]
(unsigned char)0xff, (unsigned char)0xd0, // call eax
(unsigned char)0x59, // pop ecx
(unsigned char)0x88, (unsigned char)0x04, (unsigned char)0x0f // mov [edi+ecx],al
);
break;
case '[':
SPROUT_ASSERT_MSG(loop != loop_last, "loop overflow");
*loop++ = idx; // インデックスをスタックに積む
idx += ::write_bytes(
out,
(unsigned char)0x80, (unsigned char)0x3c, (unsigned char)0x0f, (unsigned char)0x00, // cmp byte [edi+ecx],0
(unsigned char)0x0f, (unsigned char)0x84, // jz 対応する]の直後
(unsigned char)0xde, (unsigned char)0xad, (unsigned char)0xbe, (unsigned char)0xef // (アドレスは後で決定)
);
break;
case ']':
{
SPROUT_ASSERT_MSG(loop != loop_first, "missing '['");
int idx_loop = *--loop;
idx += ::write_bytes(
out,
(unsigned char)0xe9, (std::int32_t)(idx_loop - (idx + 5)) // jmp idx_loop
);
auto out_loop = out_first + (idx_loop + 6);
::write_bytes(
out_loop,
(std::int32_t)(idx - (idx_loop + 10)) // (アドレス)
);
break;
}
}
SPROUT_ASSERT_MSG(idx <= (int)::bin_size - 32, "buffer overflow");
}
SPROUT_ASSERT_MSG(loop == loop_first, "missing ']'");
// 終了処理
idx += ::write_bytes(
out,
(unsigned char)0x5f, // pop edi
(unsigned char)0x31, (unsigned char)0xc0, // xor eax, eax
(unsigned char)0xc3 // ret
);
return idx;
}
//
// ビルド
//
template<std::size_t LoopLimit = 256, typename InputIterator, typename RandomAccessIterator>
SPROUT_CXX14_CONSTEXPR std::size_t
build(InputIterator first, InputIterator last, RandomAccessIterator& out) {
std::size_t n = 0;
n += ::write_pe_header(out, n); // ヘッダ出力
n += ::write_idata(out, n); // .idataセクション出力
n += ::compile<LoopLimit>(first, last, out); // コンパイル
return n;
}
SPROUT_CXX14_CONSTEXPR sprout::sub_array<sprout::array<unsigned char, ::bin_size> >
build_brainfuck() {
sprout::array<unsigned char, ::bin_size> bin{{}};
auto out = sprout::begin(bin);
auto n = ::build<::loop_limit>(sprout::begin(::source), sprout::end(::source), out);
return sprout::sub_copy(bin, 0, n);
}
int main(int argc, char* argv[]) {
SPROUT_CXX14_CONSTEXPR auto bin = ::build_brainfuck();
char const* filename = argc >= 2 ? argv[1]
: "a.exe"
;
std::ofstream ofs(filename);
if (!ofs) {
std::cout
<< "could not open file" << std::endl
;
return -1;
}
sprout::range::copy(bin, std::ostreambuf_iterator<char>(ofs));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment