パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) C - Poem Online Judge
問題の要約
ポエムオンラインジャッジ(以下POJ)は提出された文字列に得点をつけるオンラインジャッジ。
POJにN回の提出があった。早い方からi番目の提出では文字列Siが提出されて、得点はTi。(同じ文字列が複数回提出される場合もある)
ただし、POJでは同じ文字列を提出しても得点が等しいとは限らない。
N回の提出のうち、その提出よりも早い提出であって文字列が一致するものが存在しないような提出をオリジナルであると呼ぶ。
また、オリジナルな提出の中で最も得点が高いものを最優秀賞と呼ぶ。ただし、そのような提出が複数ある場合は、最も提出が早いものを最優秀賞とする。
最優秀賞は早い方から何番目の提出か?
制約
1<=N<=10^5
Siは英小文字からなる文字列
Siの長さは1以上10以下
0<=Ti<=10^9
入力
N
S1 T1
S2 T2
...
SN TN
考え方
1,オリジナルなものだけ考えればよい。今回はmap<string,long long>mpでオリジナルかどうか調べる。
2,オリジナルなものだけになったので、同じ文字列はない。よって、文字列を管理する必要はないので、得点と何番目かを管理する。
これはvector<pair<long long,int>>Tnumで管理する。
3,Tnumを昇順でソートすると最後に一番得点が高いものが固まる。
4,しかし、何番目かも昇順でソートされているので、これから一番早いものを探さなくてはいけない。
vectorの最後の得点から確認していき、得点が違っているところのものが得点が一番高い中で一番早いもの。
実際のプログラム
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
int N;
cin >> N;
map<string, long long> mp;
vector<pair<long long, int>> Tnum;
for(int i = 1; i <= N; ++i){
string S;
long long T;
cin >> S >> T;
if(mp[S] != 0){
continue;
}
++mp[S];
Tnum.push_back(make_pair(T,i));
}
sort(Tnum.begin(),Tnum.end());
long long T = Tnum[Tnum.size()-1].first;
int ans = 1;
for(int i = Tnum.size()-1; i >= 0; --i){
if(T != Tnum[i-1].first){
ans = Tnum[i].second;
break;
}
}
cout << ans << endl;
return 0;
}
パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) B - At Most 3 (Judge ver.)
問題の要約
おもり1,おもり2,...,おもりNのN個のおもりがある。おもりiの重さはAi。
以下の条件を満たす正整数nを良い整数とよぶ。
・3個以下の異なるおもりを自由に選んで、選んだおもりの重さの和をnにすることができる。
W以下の正整数のうち、良い整数は何個あるか?
制約
1<=N<=300
1<=W<=10^6
1<=Ai<=10^6
入力
N W
A1 A2 ... AN
考え方
1,おもりの重さをvector<int>Aで管理する。
2,良い整数をvector<bool>SUMで0からWまで管理する。最初は全部false。
3,3個以下の異なるおもりを選ぶことができればよいので、3重のfor文を考え、良い整数をtrueにしていく。
おもりが1個の時はfor文の1つ目、おもりが2個の時はfor文の1つ目と2つ目、おもりが3個の時はfor文の1つ目と2つ目と3つ目に相当する。
おもりの重さの合計がW以下のものしか扱わないことに注意する。
4,SUMを0からWまでを操作してtrueのものだけをカウントする。
実際のプログラム
#include<iostream>
#include<vector>
using namespace std;
int main(){
int N,W;
cin >> N >> W;
vector<bool> SUM(W+1,false);
vector<int> A(N);
for(int i = 0; i < N; ++i){
cin >> A[i];
}
for(int i = 0; i < N; ++i){
if(A[i] <= W){
SUM[A[i]] = true;
}
for(int j = i+1; j < N; ++j){
if(A[i]+A[j] <= W){
SUM[A[i]+A[j]] = true;
}
for(int k = j+1; k < N; ++k){
if(A[i]+A[j]+A[k] <= W){
SUM[A[i]+A[j]+A[k]] = true;
}
}
}
}
int ans = 0;
for(int i = 0; i < W+1; ++i){
if(SUM[i]){
++ans;
}
}
cout << ans << endl;
return 0;
}
パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) A - Six Characters
問題の要約
英小文字からなる文字列Sが与えられる。Sの長さは1以上かつ3以下。
Sを繰り返して得られる文字列であって、長さが6のものを出力しろ。
入力
S
考え方
1、Sの長さが1、2、3のそれぞれでどうなるか考える。
Sの長さが1のとき->Sを6個つなげる。
Sの長さが2のとき->Sを3個つなげる。
Sの長さが3のとき->Sを2個つなげる。
2、Sの長さをnとして一般化できないか考える。
Sの長さがnのとき->6/n個つなげる。
実際のプログラム
#include<iostream>
#include<string>
using namespace std;
int main(){
string S;
cin >> S;
for(int i = 0; i < 6/S.size(); ++i){
cout << S;
}cout << endl;
return 0;
}
「ゼロからのOS自作入門」でMinGW-W64用のUEFIプログラムを書いてみた
この記事は、「ゼロからのOS自作入門」という書籍はLinuxとEDK2とClangで書かれているのですが、そのプログラムをWindowsとgnu-efiの一部とMinGW-W64で書いてみたという記事です。
ようやく第4章が終わったので、参考として、そこまでのソースコードを記事に載せます。
特に難しかった箇所は、3.6のAllocatePagesのエラー処理と、4.2のエントリポイントより上に関数の定義を書くところと、4.3の純粋仮想関数のところでした。
3.6では、AllocatePagesのエラー処理は必ずエラーになるので、エラー処理はコメントアウトしたら動作はしました。
4.2では、エントリポイントより上に関数の定義を書くと実行時エラーになったので、宣言と定義を分けて、定義をエントリポイントより下に書くと動作しました。
4.3では、純粋仮想関数の派生関数を呼び出すときに実行時エラーになったので、読み進めて4.5のローダの改良をすると動作しました。
[2023/2/19:追記]mingw-w64のバージョンアップによりkernel_mainが実行されなくなりました
mingw-w64をバージョンアップしたらkernel_mainが実行されなくなったので、原因を調べました。
おそらく、bootloader.cでentry_pointを呼び出す際にkernel_main関数のアドレスを呼んでいないと思われます。
なのでインラインアセンブラで対応しました。
また、kernel.elfのロードに関することで、LOADセグメントのaddressが0x0始まりだったのが、0x101000始まりになっていました。そのため、AllocatePages関数のすぐ下のコメントアウトを外してもエラーにならずに実行できました。
新しいbootloader.cのソースコードは一番下に載せています。
環境については、私のブログの「Windows10でのMinGW-w64とgnu-efiのヘッダーを使ったUEFIプログラミング」の記事を元に作業しています。
先にbootloaderとkernelのコマンドを載せます。
build_bootloader.cmd
c:\mingw64\bin\gcc.exe -fpic -ffreestanding -fno-stack-protector -fno-stack-check -fshort-wchar -mno-red-zone -maccumulate-outgoing-args -Ic:\gnu-efi\inc -Ic:\gnu-efi\inc\x86_64 -Ic:\gnu-efi\inc\protocol -Wall -c bootloader.c -o bootloader.o
c:\mingw64\bin\gcc.exe -fpic -ffreestanding -fno-stack-protector -fno-stack-check -fshort-wchar -mno-red-zone -maccumulate-outgoing-args -Ic:\gnu-efi\inc -Ic:\gnu-efi\inc\x86_64 -Ic:\gnu-efi\inc\protocol -c c:\gnu-efi\lib\data.c -o data.o
c:\mingw64\bin\gcc.exe -fpic -ffreestanding -fno-stack-protector -fno-stack-check -fshort-wchar -mno-red-zone -maccumulate-outgoing-args -Ic:\gnu-efi\inc -Ic:\gnu-efi\inc\x86_64 -Ic:\gnu-efi\inc\protocol -c bootlib.c -o bootlib.o
c:\mingw64\bin\ld.exe -nostdlib -shared -e efi_main bootloader.o data.o bootlib.o -o bootloader.bin
c:\mingw64\bin\objcopy.exe --target efi-app-x86_64 --subsystem=10 bootloader.bin BOOTX64.EFI
[2023/8/12:追記]コンパイラオプションの追加
現在、コンパイラオプションに-abi=sysvを追加しています。このオプションにすることでabiをsystem v abiに変更することができます。
build_kernel.cmd
c:\mingw64\bin\g++.exe -ffreestanding -mno-red-zone -fno-exceptions -fno-rtti -Wall -std=c++17 -g -c kernel.cpp -o kernel.o
c:\mingw64\bin\ld.exe -nostdlib -static -e kernel_main --image-base 0x100000 kernel.o -o kernel.bin
c:\mingw64\bin\objcopy.exe --target elf64-x86-64 kernel.bin kernel.elf
次にbootloder作成に必要なファイルを載せます。
elf.h
#pragma once
#include<stdint.h>
typedef uintptr_t Elf64_Addr;
typedef uint64_t Elf64_Off;
typedef uint16_t Elf64_Half;
typedef uint32_t Elf64_Word;
typedef int32_t Elf64_Sword;
typedef uint64_t Elf64_Xword;
typedef int64_t Elf64_Sxword;
#define EI_NIDENT 16
typedef struct {
unsigned char e_ident[EI_NIDENT];
Elf64_Half e_type;
Elf64_Half e_machine;
Elf64_Word e_version;
Elf64_Addr e_entry;
Elf64_Off e_phoff;
Elf64_Off e_shoff;
Elf64_Word e_flags;
Elf64_Half e_ehsize;
Elf64_Half e_phentsize;
Elf64_Half e_phnum;
Elf64_Half e_shentsize;
Elf64_Half e_shnum;
Elf64_Half e_shstrndx;
}Elf64_Ehdr;
#define ET_NONE 0
#define ET_REL 1
#define ET_EXEC 2
#define ET_DYN 3
#define ET_CORE 4
typedef struct {
Elf64_Word p_type;
Elf64_Word p_flags;
Elf64_Off p_offset;
Elf64_Addr p_vaddr;
Elf64_Addr p_paddr;
Elf64_Xword p_filesz;
Elf64_Xword p_memsz;
Elf64_Xword p_align;
}Elf64_Phdr;
#define PT_NULL 0
#define PT_LOAD 1
#define PT_DYNAMIC 2
#define PT_INTERP 3
#define PT_NOTE 4
#define PT_SHLIB 5
#define PT_PHDR 6
#define PT_TLS 7
bootlib.h
#pragma once
#include<efi.h>
#include<efilib.h>
UINTN AsciiStrLen(CHAR8* str);
CHAR8* UINT64ToAscii(UINT64 num, CHAR8* buffer);
CHAR8* UINT64ToAsciiHex(UINT64 num, CHAR8* buffer);
void AsciiFPrint(EFI_FILE_PROTOCOL* file, int n, ...);
void UnicodePrint(int n, ...);
CHAR16* AsciiToUnicode(CHAR8* ascii, CHAR16* unicode);
bootlib.c
#include<stdarg.h>
#include"bootlib.h"
UINTN AsciiStrLen(CHAR8* str){
UINTN len = 0;
while( (*str) != '\0'){
++str;
++len;
}
return len;
}
static CHAR8* itoa(UINT64 num, CHAR8* buffer, UINTN radix){
CHAR8* p = buffer;
UINT64 v = num;
int n = 1;
while(v >= radix){
v /= radix;
++n;
}
p = buffer + n;
v = num;
*p = '\0';
do{
--p;
*p = v % radix + '0';
if(*p > '9'){
*p = v % radix - 10 + 'A';
}
v /= radix;
--n;
}while(p != buffer);
return buffer;
}
CHAR8* UINT64ToAscii(UINT64 num, CHAR8* buffer){
return itoa(num,buffer,10);
}
CHAR8* UINT64ToAsciiHex(UINT64 num, CHAR8* buffer){
return itoa(num,buffer,16);
}
void AsciiFPrint(EFI_FILE_PROTOCOL* file, int n, ...){
va_list args;
va_start(args, n);
for(int i = 0; i < n; ++i){
CHAR8* str = va_arg(args, CHAR8*);
UINTN len = AsciiStrLen(str);
file->Write(file, &len, str);
}
va_end(args);
return;
}
void UnicodePrint(int n, ...){
va_list args;
va_start(args, n);
for(int i = 0; i < n; ++i){
ST->ConOut->OutputString(ST->ConOut, va_arg(args, CHAR16*));
}
va_end(args);
return;
}
CHAR16* AsciiToUnicode(CHAR8* ascii, CHAR16* unicode){
while( (*ascii) != '\0'){
*unicode = (CHAR16)*ascii;
++ascii;
++unicode;
}
*unicode = L'\0';
return unicode;
}
bootloader.c
#include<efi.h>
#include<efilib.h>
#include<limits.h>
#include"frame_buffer_config.hpp"
#include"bootlib.h"
#include"elf.h"
void ___chkstk_ms(void){
return;
}
struct MemoryMap {
UINTN buffer_size;
VOID* buffer;
UINTN map_size;
UINTN map_key;
UINTN descriptor_size;
UINT32 descriptor_version;
};
EFI_STATUS GetMemoryMap(struct MemoryMap *map){
if(map->buffer == NULL){
return EFI_BUFFER_TOO_SMALL;
}
map->map_size = map->buffer_size;
return BS->GetMemoryMap(
&map->map_size,
(EFI_MEMORY_DESCRIPTOR*)map->buffer,
&map->map_key,
&map->descriptor_size,
&map->descriptor_version);
}
const CHAR8* GetMemoryTypeAscii(EFI_MEMORY_TYPE type){
switch(type){
case EfiReservedMemoryType: return "EfiReservedMemoryType";
case EfiLoaderCode: return "EfiLoaderCode";
case EfiLoaderData: return "EfiLoaderData";
case EfiBootServicesCode: return "EfiBootServicesCode";
case EfiBootServicesData: return "EfiBootServicesData";
case EfiRuntimeServicesCode: return "EfiRuntimeServicesCode";
case EfiRuntimeServicesData: return "EfiRuntimeServicesData";
case EfiConventionalMemory: return "EfiConventionalMemory";
case EfiUnusableMemory: return "EfiUnusableMemory";
case EfiACPIReclaimMemory: return "EfiACPIReclaimMemory";
case EfiACPIMemoryNVS: return "EfiACPIMemoryNVS";
case EfiMemoryMappedIO: return "EfiMemoryMappedIO";
case EfiMemoryMappedIOPortSpace: return "EfiMemoryMappedIOPortSpace";
case EfiPalCode: return "EfiPalCode";
//case EfiPersistentMemory: return "EfiPersistentMemory";
case EfiMaxMemoryType: return "EfiMaxMemoryType";
default: return "InvalidMemoryType";
}
}
EFI_STATUS SaveMemoryMap(struct MemoryMap* map, EFI_FILE_PROTOCOL* file){
CHAR8* header = "Index, Type, Type(name), PhysicalStart, NumberOfPages, Attribute\r\n";
AsciiFPrint(file,1,header);
int i;
EFI_PHYSICAL_ADDRESS iter;
for(iter = (EFI_PHYSICAL_ADDRESS)map->buffer, i = 0; iter < (EFI_PHYSICAL_ADDRESS)map->buffer+map->map_size; iter += map->descriptor_size, i++){
EFI_MEMORY_DESCRIPTOR* desc = (EFI_MEMORY_DESCRIPTOR*)iter;
CHAR8 buffer[256];
AsciiFPrint(file,2,UINT64ToAscii(i,buffer),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->Type,buffer),",");
AsciiFPrint(file,2,GetMemoryTypeAscii(desc->Type),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->PhysicalStart,buffer),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->NumberOfPages,buffer),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->Attribute & 0xffffflu,buffer),"\r\n");
}
return EFI_SUCCESS;
}
EFI_STATUS OpenRootDir(EFI_HANDLE image_handle, EFI_FILE_PROTOCOL** root){
EFI_STATUS status;
EFI_LOADED_IMAGE_PROTOCOL* loaded_image;
EFI_SIMPLE_FILE_SYSTEM_PROTOCOL* fs;
status = BS->OpenProtocol(
image_handle,
&gEfiLoadedImageProtocolGuid,
(VOID**)&loaded_image,
image_handle,
NULL,
EFI_OPEN_PROTOCOL_BY_HANDLE_PROTOCOL);
if(EFI_ERROR(status)){
return status;
}
status = BS->OpenProtocol(
loaded_image->DeviceHandle,
&gEfiSimpleFileSystemProtocolGuid,
(VOID**)&fs,
image_handle,
NULL,
EFI_OPEN_PROTOCOL_BY_HANDLE_PROTOCOL);
if(EFI_ERROR(status)){
return status;
}
return fs->OpenVolume(fs, root);
}
EFI_STATUS OpenGOP(EFI_HANDLE image_handle, EFI_GRAPHICS_OUTPUT_PROTOCOL** gop){
EFI_STATUS status;
UINTN num_gop_handles = 0;
EFI_HANDLE* gop_handles = NULL;
status = BS->LocateHandleBuffer(
ByProtocol,
&gEfiGraphicsOutputProtocolGuid,
NULL,
&num_gop_handles,
&gop_handles);
if(EFI_ERROR(status)){
return status;
}
status = BS->OpenProtocol(
gop_handles[0],
&gEfiGraphicsOutputProtocolGuid,
(VOID**)gop,
image_handle,
NULL,
EFI_OPEN_PROTOCOL_BY_HANDLE_PROTOCOL);
if(EFI_ERROR(status)){
return status;
}
BS->FreePool(gop_handles);
return status;
}
void MyCopyMem(VOID* destination, VOID* source, UINT64 size){
char* d = (char*)destination;
char* s = (char*)source;
for(UINT64 i = 0; i < size; ++i){
d[i] = s[i];
}
}
void MySetMem(VOID* buffer, UINTN size, UINT8 value){
char *b = (char*)buffer;
for(UINTN i = 0; i < size; ++i){
b[i] = value;
}
}
void CopyLoadSegments(Elf64_Ehdr* ehdr){
Elf64_Phdr* phdr = (Elf64_Phdr*)( (UINT64)ehdr+ehdr->e_phoff);
for(Elf64_Half i = 0; i < ehdr->e_phnum; ++i){
if(phdr[i].p_type != PT_LOAD){
continue;
}
UINT64 segm_in_file = (UINT64)ehdr+phdr[i].p_offset;
MyCopyMem( (VOID*)phdr[i].p_vaddr, (VOID*)segm_in_file, phdr[i].p_filesz);
UINTN remain_bytes = phdr[i].p_memsz-phdr[i].p_filesz;
MySetMem( (VOID*)(phdr[i].p_vaddr+phdr[i].p_filesz), remain_bytes, 0);
}
}
UINT64 MIN(UINT64 now, UINT64 next){
return ( now < next ? now : next);
}
UINT64 MAX(UINT64 now, UINT64 next){
return ( now < next ? next : now);
}
void CalcLoadAddressRange(Elf64_Ehdr* ehdr, UINT64* first, UINT64* last){
Elf64_Phdr* phdr = (Elf64_Phdr*)( (UINT64)ehdr+ehdr->e_phoff);
*first = ULLONG_MAX;
*last = 0;
for(Elf64_Half i = 0; i < ehdr->e_phnum; ++i){
if(phdr[i].p_type != PT_LOAD){
continue;
}
*first = MIN(*first, phdr[i].p_vaddr);
*last = MAX(*last, phdr[i].p_vaddr+phdr[i].p_memsz);
}
}
EFI_STATUS efi_main(EFI_HANDLE ImageHandle, EFI_SYSTEM_TABLE *SystemTable){
EFI_STATUS Status;
ST = SystemTable;
BS = SystemTable->BootServices;
Status = ST->ConOut->OutputString(ST->ConOut, L"Hello World!\r\n");
if(EFI_ERROR(Status)){
return Status;
}
// get gop
EFI_GRAPHICS_OUTPUT_PROTOCOL* gop;
OpenGOP(ImageHandle, &gop);
UINT8* frame_buffer = (UINT8*)gop->Mode->FrameBufferBase;
for(UINTN i = 0; i < gop->Mode->FrameBufferSize; ++i){
frame_buffer[i] = 255;
}
// config
struct FrameBufferConfig config = {
(UINT8*)gop->Mode->FrameBufferBase,
gop->Mode->Info->PixelsPerScanLine,
gop->Mode->Info->HorizontalResolution,
gop->Mode->Info->VerticalResolution,
0};
switch(gop->Mode->Info->PixelFormat){
case PixelRedGreenBlueReserved8BitPerColor:
config.pixel_format = kPixelRGBResv8BitPerColor;
break;
case PixelBlueGreenRedReserved8BitPerColor:
config.pixel_format = kPixelBGRResv8BitPerColor;
break;
default:
UnicodePrint(1,L"Unimplemented pixel format.\r\n");
while(1){}
}
UnicodePrint(1,L"config_end\r\n");
// write memmap
CHAR8 memmap_buf[4096*4];
struct MemoryMap memmap = {sizeof(memmap_buf),memmap_buf,0,0,0,0};
Status = GetMemoryMap(&memmap);
if(EFI_ERROR(Status)){
ST->ConOut->OutputString(ST->ConOut, L"failed to get memory map:\r\n");
return Status;
}
EFI_FILE_PROTOCOL* root_dir;
OpenRootDir(ImageHandle, &root_dir);
EFI_FILE_PROTOCOL* memmap_file;
root_dir->Open(
root_dir,
&memmap_file,
L"\\memmap",
EFI_FILE_MODE_READ | EFI_FILE_MODE_WRITE | EFI_FILE_MODE_CREATE,
0);
SaveMemoryMap(&memmap, memmap_file);
memmap_file->Close(memmap_file);
UnicodePrint(1,L"memmap_end\r\n");
// read kernel file version 1
/*
EFI_FILE_PROTOCOL* kernel_file;
root_dir->Open(root_dir, &kernel_file, L"\\kernel.elf", EFI_FILE_MODE_READ, 0);
UINTN file_info_size = sizeof(EFI_FILE_INFO)+sizeof(CHAR16)*12;
UINT8 file_info_buffer[file_info_size];
kernel_file->GetInfo(kernel_file, &gEfiFileInfoGuid, &file_info_size, file_info_buffer);
EFI_FILE_INFO* file_info = (EFI_FILE_INFO*)file_info_buffer;
UINTN kernel_file_size = file_info->FileSize;
EFI_PHYSICAL_ADDRESS kernel_base_addr = 0x100000;
BS->AllocatePages(AllocateAddress, EfiLoaderData, (kernel_file_size+0xfff)/0x1000, &kernel_base_addr);
kernel_file->Read(kernel_file, &kernel_file_size, (VOID*)kernel_base_addr);
CHAR8 ascii_buffer[256];
CHAR16 unicode_buffer[256];
UnicodePrint(1,L"kernel: ");
UINT64ToAsciiHex(kernel_base_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L",");
UINT64ToAscii(kernel_file_size,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L"\r\n");
*/
// read kernel file version 2
EFI_FILE_PROTOCOL* kernel_file;
root_dir->Open(root_dir, &kernel_file, L"\\kernel.elf", EFI_FILE_MODE_READ, 0);
UINTN file_info_size = sizeof(EFI_FILE_INFO)+sizeof(CHAR16)*12;
UINT8 file_info_buffer[file_info_size];
kernel_file->GetInfo(kernel_file, &gEfiFileInfoGuid, &file_info_size, file_info_buffer);
EFI_FILE_INFO* file_info = (EFI_FILE_INFO*)file_info_buffer;
UINTN kernel_file_size = file_info->FileSize;
VOID* kernel_buffer;
Status = BS->AllocatePool(EfiLoaderData, kernel_file_size, &kernel_buffer);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to allocate pool.\r\n");
while(1){}
}
Status = kernel_file->Read(kernel_file, &kernel_file_size, kernel_buffer);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"error.\r\n");
while(1){}
}
Elf64_Ehdr* kernel_ehdr = (Elf64_Ehdr*)kernel_buffer;
UINT64 kernel_first_addr, kernel_last_addr;
CalcLoadAddressRange(kernel_ehdr, &kernel_first_addr, &kernel_last_addr);
UINTN num_pages = (kernel_last_addr-kernel_first_addr+0xfff)/0x1000;
Status = BS->AllocatePages(AllocateAddress, EfiLoaderData, num_pages, &kernel_first_addr);
/*if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to allocate pages.\r\n");
while(1){}
}*/
CopyLoadSegments(kernel_ehdr);
Status = BS->FreePool(kernel_buffer);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to free pool.\r\n");
while(1){}
}
CHAR8 ascii_buffer[256];
CHAR16 unicode_buffer[256];
UnicodePrint(1,L"kernel: ");
UINT64ToAsciiHex(kernel_first_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L" - ");
UINT64ToAscii(kernel_last_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L"\r\n");
// exit bootservices
Status = BS->ExitBootServices(ImageHandle, memmap.map_key);
if(EFI_ERROR(Status)){
Status = GetMemoryMap(&memmap);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to get memory map.\r\n");
while(1){}
}
Status = BS->ExitBootServices(ImageHandle, memmap.map_key);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"Could not exit boot service.\r\n");
while(1){}
}
}
// entry kernel
UINT64 entry_addr = *(UINT64*)(kernel_first_addr+24);
typedef void EntryPointType(const struct FrameBufferConfig*);
EntryPointType* entry_point = (EntryPointType*)entry_addr;
entry_point(&config);
while(1){
}
return Status;
}
次にkernel作成に必要なファイルを載せます。
frame_buffer_config,hpp
#pragma once
#include<stdint.h>
enum PixelFormat{
kPixelRGBResv8BitPerColor,
kPixelBGRResv8BitPerColor,
};
struct FrameBufferConfig{
uint8_t* frame_buffer;
uint32_t pixels_per_scan_line;
uint32_t horizontal_resolution;
uint32_t vertical_resolution;
enum PixelFormat pixel_format;
};
kernel.cpp
#include<cstdint>
#include<cstddef>
#include<new>
#include"frame_buffer_config.hpp"
struct PixelColor{
uint8_t r;
uint8_t g;
uint8_t b;
};
void operator delete(void* obj, unsigned long long arg)noexcept;
class PixelWriter{
public:
PixelWriter(const FrameBufferConfig& config);
virtual ~PixelWriter() = default;
virtual void Write(uint32_t x, uint32_t y, const PixelColor& c) = 0;
protected:
uint8_t* PixelAt(uint32_t x, uint32_t y);
private:
const FrameBufferConfig& config_;
};
class RGBResc8BitPerColorPixelWriter : public PixelWriter{
public:
using PixelWriter::PixelWriter;
virtual void Write(uint32_t x, uint32_t y, const PixelColor& c);
};
class BGRResc8BitPerColorPixelWriter : public PixelWriter{
public:
using PixelWriter::PixelWriter;
virtual void Write(uint32_t x, uint32_t y, const PixelColor& c);
};
char pixel_writer_buf[sizeof(RGBResc8BitPerColorPixelWriter)];
PixelWriter* pixel_writer;
extern "C" void kernel_main(const FrameBufferConfig& frame_buffer_config){
switch(frame_buffer_config.pixel_format){
case kPixelRGBResv8BitPerColor:
pixel_writer = new(pixel_writer_buf)RGBResc8BitPerColorPixelWriter{frame_buffer_config};
break;
case kPixelBGRResv8BitPerColor:
pixel_writer = new(pixel_writer_buf)BGRResc8BitPerColorPixelWriter{frame_buffer_config};
break;
}
for(uint32_t x = 0; x < frame_buffer_config.horizontal_resolution; ++x){
for(uint32_t y = 0; y < frame_buffer_config.vertical_resolution; ++y){
pixel_writer->Write(x,y,{255,255,255});
}
}
for(uint32_t x = 0; x < 200; ++x){
for(uint32_t y = 0; y < 100; ++y){
pixel_writer->Write(x,y,{0,255,0});
}
}
while(true){
__asm__("hlt");
}
return;
}
void operator delete(void* obj, unsigned long long arg)noexcept{}
PixelWriter::PixelWriter(const FrameBufferConfig& config) : config_{config}{}
uint8_t* PixelWriter::PixelAt(uint32_t x, uint32_t y){
return &config_.frame_buffer[4*(config_.pixels_per_scan_line*y+x)];
}
void RGBResc8BitPerColorPixelWriter::Write(uint32_t x, uint32_t y, const PixelColor& c){
uint8_t* p = PixelAt(x,y);
p[0] = c.r;
p[1] = c.g;
p[2] = c.b;
}
void BGRResc8BitPerColorPixelWriter::Write(uint32_t x, uint32_t y, const PixelColor& c){
uint8_t* p = PixelAt(x,y);
p[0] = c.b;
p[1] = c.g;
p[2] = c.r;
}
これでWindowsでもC++でUEFIのOS自作ができるようになると思います。
[2023/2/19:追記]新しいbootloader.c
bootloader.c
#include<efi.h>
#include<efilib.h>
#include<limits.h>
#include"frame_buffer_config.hpp"
#include"bootlib.h"
#include"elf.h"
void ___chkstk_ms(void){
return;
}
struct MemoryMap {
UINTN buffer_size;
VOID* buffer;
UINTN map_size;
UINTN map_key;
UINTN descriptor_size;
UINT32 descriptor_version;
};
EFI_STATUS GetMemoryMap(struct MemoryMap *map){
if(map->buffer == NULL){
return EFI_BUFFER_TOO_SMALL;
}
map->map_size = map->buffer_size;
return BS->GetMemoryMap(
&map->map_size,
(EFI_MEMORY_DESCRIPTOR*)map->buffer,
&map->map_key,
&map->descriptor_size,
&map->descriptor_version);
}
const CHAR8* GetMemoryTypeAscii(EFI_MEMORY_TYPE type){
switch(type){
case EfiReservedMemoryType: return "EfiReservedMemoryType";
case EfiLoaderCode: return "EfiLoaderCode";
case EfiLoaderData: return "EfiLoaderData";
case EfiBootServicesCode: return "EfiBootServicesCode";
case EfiBootServicesData: return "EfiBootServicesData";
case EfiRuntimeServicesCode: return "EfiRuntimeServicesCode";
case EfiRuntimeServicesData: return "EfiRuntimeServicesData";
case EfiConventionalMemory: return "EfiConventionalMemory";
case EfiUnusableMemory: return "EfiUnusableMemory";
case EfiACPIReclaimMemory: return "EfiACPIReclaimMemory";
case EfiACPIMemoryNVS: return "EfiACPIMemoryNVS";
case EfiMemoryMappedIO: return "EfiMemoryMappedIO";
case EfiMemoryMappedIOPortSpace: return "EfiMemoryMappedIOPortSpace";
case EfiPalCode: return "EfiPalCode";
//case EfiPersistentMemory: return "EfiPersistentMemory";
case EfiMaxMemoryType: return "EfiMaxMemoryType";
default: return "InvalidMemoryType";
}
}
EFI_STATUS SaveMemoryMap(struct MemoryMap* map, EFI_FILE_PROTOCOL* file){
CHAR8* header = "Index, Type, Type(name), PhysicalStart, NumberOfPages, Attribute\r\n";
AsciiFPrint(file,1,header);
int i;
EFI_PHYSICAL_ADDRESS iter;
for(iter = (EFI_PHYSICAL_ADDRESS)map->buffer, i = 0; iter < (EFI_PHYSICAL_ADDRESS)map->buffer+map->map_size; iter += map->descriptor_size, i++){
EFI_MEMORY_DESCRIPTOR* desc = (EFI_MEMORY_DESCRIPTOR*)iter;
CHAR8 buffer[256];
AsciiFPrint(file,2,UINT64ToAscii(i,buffer),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->Type,buffer),",");
AsciiFPrint(file,2,GetMemoryTypeAscii(desc->Type),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->PhysicalStart,buffer),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->NumberOfPages,buffer),",");
AsciiFPrint(file,2,UINT64ToAsciiHex(desc->Attribute & 0xffffflu,buffer),"\r\n");
}
return EFI_SUCCESS;
}
EFI_STATUS OpenRootDir(EFI_HANDLE image_handle, EFI_FILE_PROTOCOL** root){
EFI_STATUS status;
EFI_LOADED_IMAGE_PROTOCOL* loaded_image;
EFI_SIMPLE_FILE_SYSTEM_PROTOCOL* fs;
status = BS->OpenProtocol(
image_handle,
&gEfiLoadedImageProtocolGuid,
(VOID**)&loaded_image,
image_handle,
NULL,
EFI_OPEN_PROTOCOL_BY_HANDLE_PROTOCOL);
if(EFI_ERROR(status)){
return status;
}
status = BS->OpenProtocol(
loaded_image->DeviceHandle,
&gEfiSimpleFileSystemProtocolGuid,
(VOID**)&fs,
image_handle,
NULL,
EFI_OPEN_PROTOCOL_BY_HANDLE_PROTOCOL);
if(EFI_ERROR(status)){
return status;
}
return fs->OpenVolume(fs, root);
}
EFI_STATUS OpenGOP(EFI_HANDLE image_handle, EFI_GRAPHICS_OUTPUT_PROTOCOL** gop){
EFI_STATUS status;
UINTN num_gop_handles = 0;
EFI_HANDLE* gop_handles = NULL;
status = BS->LocateHandleBuffer(
ByProtocol,
&gEfiGraphicsOutputProtocolGuid,
NULL,
&num_gop_handles,
&gop_handles);
if(EFI_ERROR(status)){
return status;
}
status = BS->OpenProtocol(
gop_handles[0],
&gEfiGraphicsOutputProtocolGuid,
(VOID**)gop,
image_handle,
NULL,
EFI_OPEN_PROTOCOL_BY_HANDLE_PROTOCOL);
if(EFI_ERROR(status)){
return status;
}
BS->FreePool(gop_handles);
return status;
}
void MyCopyMem(VOID* destination, VOID* source, UINT64 size){
char* d = (char*)destination;
char* s = (char*)source;
for(UINT64 i = 0; i < size; ++i){
d[i] = s[i];
}
}
void MySetMem(VOID* buffer, UINT64 size, UINT8 value){
char *b = (char*)buffer;
for(UINT64 i = 0; i < size; ++i){
b[i] = value;
}
}
void CopyLoadSegments(Elf64_Ehdr* ehdr){
Elf64_Phdr* phdr = (Elf64_Phdr*)( (UINT64)ehdr+ehdr->e_phoff);
for(Elf64_Half i = 0; i < ehdr->e_phnum; ++i){
if(phdr[i].p_type != PT_LOAD){
continue;
}
UINT64 segm_in_file = (UINT64)ehdr+phdr[i].p_offset;
MyCopyMem( (VOID*)phdr[i].p_vaddr, (VOID*)segm_in_file, phdr[i].p_filesz);
UINT64 remain_bytes = phdr[i].p_memsz-phdr[i].p_filesz;
MySetMem( (VOID*)(phdr[i].p_vaddr+phdr[i].p_filesz), remain_bytes, 0);
}
}
UINT64 MIN(UINT64 now, UINT64 next){
return ( now < next ? now : next);
}
UINT64 MAX(UINT64 now, UINT64 next){
return ( now < next ? next : now);
}
void CalcLoadAddressRange(Elf64_Ehdr* ehdr, UINT64* first, UINT64* last){
Elf64_Phdr* phdr = (Elf64_Phdr*)( (UINT64)ehdr+ehdr->e_phoff);
*first = ULLONG_MAX;
*last = 0;
for(Elf64_Half i = 0; i < ehdr->e_phnum; ++i){
if(phdr[i].p_type != PT_LOAD){
continue;
}
*first = MIN(*first, phdr[i].p_vaddr);
*last = MAX(*last, phdr[i].p_vaddr+phdr[i].p_memsz);
}
}
EFI_STATUS efi_main(EFI_HANDLE ImageHandle, EFI_SYSTEM_TABLE *SystemTable){
EFI_STATUS Status;
ST = SystemTable;
BS = SystemTable->BootServices;
Status = ST->ConOut->OutputString(ST->ConOut, L"Hello World!\r\n");
if(EFI_ERROR(Status)){
return Status;
}
// get gop
EFI_GRAPHICS_OUTPUT_PROTOCOL* gop;
OpenGOP(ImageHandle, &gop);
UINT8* frame_buffer = (UINT8*)gop->Mode->FrameBufferBase;
for(UINTN i = 0; i < gop->Mode->FrameBufferSize; ++i){
frame_buffer[i] = 255;
}
// config
struct FrameBufferConfig config = {
(UINT8*)gop->Mode->FrameBufferBase,
gop->Mode->Info->PixelsPerScanLine,
gop->Mode->Info->HorizontalResolution,
gop->Mode->Info->VerticalResolution,
0};
switch(gop->Mode->Info->PixelFormat){
case PixelRedGreenBlueReserved8BitPerColor:
config.pixel_format = kPixelRGBResv8BitPerColor;
break;
case PixelBlueGreenRedReserved8BitPerColor:
config.pixel_format = kPixelBGRResv8BitPerColor;
break;
default:
UnicodePrint(1,L"Unimplemented pixel format.\r\n");
while(1){}
}
UnicodePrint(1,L"config_end\r\n");
// write memmap
CHAR8 memmap_buf[4096*4];
struct MemoryMap memmap = {sizeof(memmap_buf),memmap_buf,0,0,0,0};
Status = GetMemoryMap(&memmap);
if(EFI_ERROR(Status)){
ST->ConOut->OutputString(ST->ConOut, L"failed to get memory map:\r\n");
return Status;
}
EFI_FILE_PROTOCOL* root_dir;
OpenRootDir(ImageHandle, &root_dir);
EFI_FILE_PROTOCOL* memmap_file;
root_dir->Open(
root_dir,
&memmap_file,
L"\\memmap",
EFI_FILE_MODE_READ | EFI_FILE_MODE_WRITE | EFI_FILE_MODE_CREATE,
0);
SaveMemoryMap(&memmap, memmap_file);
memmap_file->Close(memmap_file);
UnicodePrint(1,L"memmap_end\r\n");
// read kernel file version 1
/*
EFI_FILE_PROTOCOL* kernel_file;
root_dir->Open(root_dir, &kernel_file, L"\\kernel.elf", EFI_FILE_MODE_READ, 0);
UINTN file_info_size = sizeof(EFI_FILE_INFO)+sizeof(CHAR16)*12;
UINT8 file_info_buffer[file_info_size];
kernel_file->GetInfo(kernel_file, &gEfiFileInfoGuid, &file_info_size, file_info_buffer);
EFI_FILE_INFO* file_info = (EFI_FILE_INFO*)file_info_buffer;
UINTN kernel_file_size = file_info->FileSize;
EFI_PHYSICAL_ADDRESS kernel_base_addr = 0x100000;
BS->AllocatePages(AllocateAddress, EfiLoaderData, (kernel_file_size+0xfff)/0x1000, &kernel_base_addr);
kernel_file->Read(kernel_file, &kernel_file_size, (VOID*)kernel_base_addr);
CHAR8 ascii_buffer[256];
CHAR16 unicode_buffer[256];
UnicodePrint(1,L"kernel: ");
UINT64ToAsciiHex(kernel_base_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L",");
UINT64ToAscii(kernel_file_size,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L"\r\n");
*/
// read kernel file version 2
EFI_FILE_PROTOCOL* kernel_file;
Status = root_dir->Open(root_dir, &kernel_file, L"\\kernel.elf", EFI_FILE_MODE_READ, 0);
if(EFI_ERROR(Status)){
UnicodePrint(1,L"failed to open file.\r\n");
while(1){}
}
UINTN file_info_size = sizeof(EFI_FILE_INFO)+sizeof(CHAR16)*12;
UINT8 file_info_buffer[file_info_size];
kernel_file->GetInfo(kernel_file, &gEfiFileInfoGuid, &file_info_size, file_info_buffer);
EFI_FILE_INFO* file_info = (EFI_FILE_INFO*)file_info_buffer;
UINTN kernel_file_size = file_info->FileSize;
VOID* kernel_buffer;
Status = BS->AllocatePool(EfiLoaderData, kernel_file_size, &kernel_buffer);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to allocate pool.\r\n");
while(1){}
}
Status = kernel_file->Read(kernel_file, &kernel_file_size, kernel_buffer);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"error.\r\n");
while(1){}
}
Elf64_Ehdr* kernel_ehdr = (Elf64_Ehdr*)kernel_buffer;
UINT64 kernel_first_addr = ULLONG_MAX;
UINT64 kernel_last_addr = 0;
CalcLoadAddressRange(kernel_ehdr, &kernel_first_addr, &kernel_last_addr);
UINTN num_pages = (kernel_last_addr-kernel_first_addr+0xfff)/0x1000;
Status = BS->AllocatePages(AllocateAddress, EfiLoaderData, num_pages, &kernel_first_addr);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to allocate pages.\r\n");
while(1){}
}
CopyLoadSegments(kernel_ehdr);
UINT64 kernel_entry_addr = kernel_ehdr->e_entry;
Status = BS->FreePool(kernel_buffer);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to free pool.\r\n");
while(1){}
}
{
CHAR8 ascii_buffer[256];
CHAR16 unicode_buffer[256];
UnicodePrint(1,L"entry_addr: ");
UINT64ToAsciiHex(kernel_entry_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L"\r\n");
}
{
CHAR8 ascii_buffer[256];
CHAR16 unicode_buffer[256];
UnicodePrint(1,L"kernel: ");
UINT64ToAsciiHex(kernel_first_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L" - ");
}
{
CHAR8 ascii_buffer[256];
CHAR16 unicode_buffer[256];
UINT64ToAsciiHex(kernel_last_addr,ascii_buffer);
AsciiToUnicode(ascii_buffer,unicode_buffer);
UnicodePrint(1,unicode_buffer);
UnicodePrint(1,L"\r\n");
}
// exit bootservices
Status = BS->ExitBootServices(ImageHandle, memmap.map_key);
if(EFI_ERROR(Status)){
Status = GetMemoryMap(&memmap);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"failed to get memory map.\r\n");
while(1){}
}
Status = BS->ExitBootServices(ImageHandle, memmap.map_key);
if(EFI_ERROR(Status)){
UnicodePrint(1, L"Could not exit boot service.\r\n");
while(1){}
}
}
// entry kernel
//UINT64 entry_addr = *(UINT64*)(kernel_first_addr+24);
//UINT64 entry_addr = *(UINT64*)(kernel_entry_addr);
//typedef void EntryPointType(const struct FrameBufferConfig*);
//EntryPointType* entry_point = (EntryPointType*)entry_addr;
//entry_point(&config);
__asm__("mov %0, %%rcx"::"r"(&config):"%rcx");
__asm__("mov %0, %%rax"::"r"(kernel_entry_addr):"%rax");
__asm__("jmp *%rax");
while(1){
__asm__("hlt");
}
return Status;
}
Windows10でのMinGW-w64とgnu-efiのヘッダーを使ったUEFIプログラミング
Windows10でMinGW-w64とgnu-efiを使ったUEFIプログラミングがしたかったので、「hello world」を表示させるところまでの手順を載せます。
注意としては、gnu-efiの一部のファイルだけを使っているので、gnu-efiの関数を使えるかはわからないです。
1.7-Zip.exeのダウンロードとインストール
7-Zip
へ行って、
.exeの64-bit x64の
Downloadをクリックして、exeファイルをダウンロードします。
「7z2107-x64.exe」がダウンロードされたので、これをダブルクリックしてインストールします。
2.Mingw-w64のダウンロードと解凍
WinLibs standalone build of GCC and MinGW-w64 for Windows
へ行って、
GCC 11.2.0 + MinGW-w64 10.0.0 (UCRT)のWin64の
7-Zip archive
をクリックして、7zファイルをダウンロードします。
「winlibs-x86_64-posix-seh-gcc-11.2.0-mingw-w64ucrt-10.0.0-r1.7z」というファイルがダウンロードされるので、これを解凍します。
解凍したら、「mingw64」というファイルができるので、このファイルをCドライブの直下に移動させます。
3.gnu-efiのダウンロードと解凍とdata.cファイルの変更
sourceforgeのgnu-efi
https://sourceforge.net/projects/gnu-efi/
へ行って
Download
をクリックして、tar.bz2ファイルをダウンロードします。
「gnu-efi-3.0.14.tar.bz2」というファイルがダウンロードされるので、これを展開します。
展開したら「gnu-efi-3.0.14.tar」というファイルができるので、これを展開します。
展開したら「gnu-efi-3.0.14」というファイルができるので、これを名前を「gnu-efi」にして、Cドライブの直下に移動させます。
data.cファイルを変更します。
C:\gnu-efi\lib\data.cの
EFI_UNICODE_COLLATION_INTERFACE LibStubUnicodeInterface = {
LibStubStriCmp,
LibStubMetaiMatch,
LibStubStrLwrUpr,
LibStubStrLwrUpr,
NULL, // FatToStr
NULL, // StrToFat
NULL // SupportedLanguages
};
を
EFI_UNICODE_COLLATION_INTERFACE LibStubUnicodeInterface = {
NULL,
NULL,
NULL,
NULL,
NULL, // FatToStr
NULL, // StrToFat
NULL // SupportedLanguages
};
に変えます。
4.VMwareのダウンロードとインストールと仮想マシンの作成とvmxファイルの変更
Download VMware Workstation Player
https://www.vmware.com/products/workstation-player/workstation-player-evaluation.html
へ行って、
Try Workstation 16.0 Player for Windowsの
DOWNLOAD NOW
をクリックして、exeファイルをダウンロードします。
「VMware-player-full-16.2.3-19376536.exe」というファイルがダウンロードされるので、これをクリックしてインストールします。
新規仮想マシンの作成をクリックして
「後でOSをインストール」にチェックを入れて次へをクリック、
ゲストOSは「その他」、バージョンは「他の64ビット」にして次へをクリック、
仮想マシン名を決めて、場所(デフォルトで"C:\Users\username(ここに自分のユーザ名が入る)\Documents\Virtual Machines\仮想マシン名"となっている)を決め、次へをクリック、
ディスク容量の指定はデフォルトのままで次へをクリック、
ハードウェアをカスタマイズを押して、追加を押し、USBコントローラを追加し、USBの互換性を「USB3.1」にして、次へをクリック、
そして完了をクリックします。
決めた場所のフォルダまで行き、vmxファイルに
firmware = "efi"
を追加します。
5.フォルダの作成
作業用フォルダを作成します。
6.main.cファイルの作成
作業用フォルダ内にmain.cというファイルを作成します。
https://wiki.osdev.org/UEFI_Bare_Bones
のhello.cの内容をmain.cに書きます。
7.バッチファイルの作成とBOOTX64.EFIの作成
build.cmdというファイルを作成し、
c:\mingw64\bin\gcc.exe -fpic -ffreestanding -fno-stack-protector -fno-stack-check -fshort-wchar -mno-red-zone -maccumulate-outgoing-args -Ic:\gnu-efi\inc -Ic:\gnu-efi\inc\x86_64 -Ic:\gnu-efi\inc\protocol -c main.c -o main.o
c:\mingw64\bin\gcc.exe -fpic -ffreestanding -fno-stack-protector -fno-stack-check -fshort-wchar -mno-red-zone -maccumulate-outgoing-args -Ic:\gnu-efi\inc -Ic:\gnu-efi\inc\x86_64 -Ic:\gnu-efi\inc\protocol -c c:\gnu-efi\lib\data.c -o data.o
c:\mingw64\bin\ld.exe -nostdlib -shared -e efi_main main.o data.o -o BOOTX64.bin
c:\mingw64\bin\objcopy.exe --target efi-app-x86_64 --subsystem=10 BOOTX64.bin BOOTX64.EFI
を書き、保存します。
build.cmdをクリックし、BOOTX64.EFIを作成します。
8.BOOTX64.EFIをUSBメモリにコピー
BOOT64.EFIをUSBメモリの
「EFI\BOOT」にコピーします。
9.VMwareからの起動
VMwareを起動します。
USBメモリがVMwareに接続されているかは
Player->取り外し可能デバイス
でわかります。USBメモリが接続されていない場合も上記の場所から接続できます。
これでVMware上に"Hello World"が表示されると思います。
AtCoder Beginner Contest 246 C - Coupon
問題の要約
N個の商品がある。i=1,...,Nについて、i番目の商品の値段はAi円。
今、K枚のクーポンを持っている。
1枚のクーポンは1つの商品に対して使用することができ、1つの商品に対してはクーポンを何枚でも(0枚でもよい)使用することができる。
値段がa円の商品に対してk枚のクーポンを使用すると、その商品をmax{a-kX,0}円で買うことができる。
すべての商品を買うために支払う合計金額の最小値を出力せよ。
制約
1<=N<=2*10^5
1<=K,X<=10^9
1<=Ai<=10^9
入力
N K X
A1 ... AN
考え方
1,a<=Xのような場合、そのようなどの商品に対してクーポンを使っても最小値は変わらない。
よって、X<aとなるように全ての商品にクーポンを使っていく。
2,この時点で全ての商品はX<aである。このとき、aがXに近い値(すなわちより高い値段)の商品にクーポンを使った方が合計金額が小さいくなる。
よって、全ての商品を降順でソートして、順にクーポンを使っていく。
3,合計金額を計算して、出力する。
実際のプログラム
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
long long N,K,X;
cin >> N >> K >> X;
vector<long long> A(N);
for(long long i = 0; i < N; ++i){
cin >> A[i];
}
for(long long i = 0; i < N; ++i){
long long k = A[i] / X;
if(k != 0){
A[i] = A[i] - min(k,K) * X;
K -= min(k,K);
}
}
sort(A.begin(),A.end());
reverse(A.begin(),A.end());
for(long long i = 0; i < N; ++i){
if(K != 0){
A[i] -= A[i];
K--;
}
}
long long ans = 0;
for(long long i = 0; i < N; ++i){
ans += A[i];
}
cout << ans << endl;
return 0;
}
AtCoder Beginner Contest 246 B - Get Closer
問題の要約
二次元平面上の点(0,0)から点(A,B)に向かって距離1だけ移動する。
移動後の座標を求めよ。
なお、制約より点(0,0)と点(A,B)の距離は1以上であることが保証される。
制約
入力は全て整数
0<=A,B<=1000
(A,B)≠(0,0)
入力
A B
出力
移動後の点を(x,y)とするとき、xとyをこの順に空白区切りで出力せよ。
想定解との絶対誤差または相対誤差が10^-6以下であれば正解として扱われる。
考え方
1,(A,B)方向に距離1移動した後の点を(A',B')とする。
1 = sqrt(A'^2+B'^2)である。
2,(A,B)に移動したときの距離をdとする。
d = sqrt(A^2+B^2)である。
3,比で考える。
A:B:d = A':B':1より
A:d = A':1
B:d = B':1
これより
A' = A/d
B' = B/d
実際のプログラム
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
double A,B;
cin >> A >> B;
double A_ = A / sqrt(A*A+B*B);
double B_ = B / sqrt(A*A+B*B);
cout << setprecision(15) << A_ << " " << B_ << endl;
return 0;
}