ARC101 C candles
やっぱ難しいなぁ、競プロ。
左右に行ききするタイプ＋k個連続のスリットのようなものを動かすみたいなイメージ。
この方のwiteupを見た。 スリットを動かすみたいのはわかったけど、コードに落とせなかった。
以下、pythonで書いたもの。全く同じ(正確には違う)で載せるのも憚られるのですが、すみません。
def main(): n,k = [int(i) for i in input().split()] candles = [int(i) for i in input().split()] i = 0 res=1<<60; while i+k-1<n: left = candles[i] right = candles[i+k-1] res = min(res,min(abs(left),abs(right))+right-left) i+=1 print(res) if __name__ == '__main__': main()
min(abs(left),abs(right))+(right-left)
この部分は(right-left)でこの区間を走査する時間でabsではじめに右に行くか左に行くか決めてるっぽい。 イメージはある区間の一番端に一度行って、逆の端に走って行くという感じ。
学んだこと
- 個数が決まったスリットの動かし方
- 考え方
最初、0からスタートするし、0 に一番近いところから取ってって...と考えていたので、その時点で方向性が違ったように感じる。久々に、C解けなかったなぁ。自信なくすなぁ。
pwnable.kr(7)(2) ~input~
前回の続きです。
ステージ 2 からやっていきます。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/socket.h> #include <arpa/inet.h> int main(int argc, char* argv[], char* envp[]){ printf("Welcome to pwnable.kr\n"); printf("Let's see if you know how to give input to program\n"); printf("Just give me correct inputs then you will get the flag :)\n"); // argv if(argc != 100) return 0; if(strcmp(argv['A'],"\x00")) return 0; if(strcmp(argv['B'],"\x20\x0a\x0d")) return 0; printf("Stage 1 clear!\n"); // stdio char buf[4]; read(0, buf, 4); if(memcmp(buf, "\x00\x0a\x00\xff", 4)) return 0; read(2, buf, 4); if(memcmp(buf, "\x00\x0a\x02\xff", 4)) return 0; printf("Stage 2 clear!\n"); // env if(strcmp("\xca\xfe\xba\xbe", getenv("\xde\xad\xbe\xef"))) return 0; printf("Stage 3 clear!\n"); // file FILE* fp = fopen("\x0a", "r"); if(!fp) return 0; if( fread(buf, 4, 1, fp)!=1 ) return 0; if( memcmp(buf, "\x00\x00\x00\x00", 4) ) return 0; fclose(fp); printf("Stage 4 clear!\n"); // network int sd, cd; struct sockaddr_in saddr, caddr; sd = socket(AF_INET, SOCK_STREAM, 0); if(sd == -1){ printf("socket error, tell admin\n"); return 0; } saddr.sin_family = AF_INET; saddr.sin_addr.s_addr = INADDR_ANY; saddr.sin_port = htons( atoi(argv['C']) ); if(bind(sd, (struct sockaddr*)&saddr, sizeof(saddr)) < 0){ printf("bind error, use another port\n"); return 1; } listen(sd, 1); int c = sizeof(struct sockaddr_in); cd = accept(sd, (struct sockaddr *)&caddr, (socklen_t*)&c); if(cd < 0){ printf("accept error, tell admin\n"); return 0; } if( recv(cd, buf, 4, 0) != 4 ) return 0; if(memcmp(buf, "\xde\xad\xbe\xef", 4)) return 0; printf("Stage 5 clear!\n"); // here's your flag system("/bin/cat flag"); return 0; }
とりあえずコード貼っておく。 ステージ2は標準入出力周り。 単純にsys.stdin.writeとsys.stderr.writeが使えなかった。結局パイプを使う方法がいいみたいだ。forkでexecだと、stdinとstderrをパイプに接続できないので、subprocessのプロセスオープンで対応。
stdinr, stdinw = os.pipe()
stderrr, stderrw = os.pipe()
os.write(stdinw, "\x00\x0a\x00\xff")
os.write(stderrw, "\x00\x0a\x02\xff")
パイプを作って書き込む。シェルからかくとヌル文字で区切られてしまうので書き込むことができないようだ。低水準は奥が深いなぁ。
ステージ3は唯一書き込み可能な /tmpディレクトリで行わなければならない。chdirをすることを最初考えて進めていたが、あとでダメだということがわかった（これめちゃめちゃ重要だった）なので、/tmpで自分のディレクトリを作って、その中で実行というのが正解みたいだ。ステージ3、4、5は初見で突破できた。以下ステージ3、4、5の
f = open("\x0a","w") f.write("\x00\x00\x00\x00") f.close() args[ord("C")-1] = '1234' subprocess.Popen(["/home/input2/input"]+args,stdin=stdinr,stderr=stderrr) time.sleep(1) sock = socket.socket(family=socket.AF_INET,type=socket.SOCK_STREAM) sock.connect(('127.0.0.1',1234)) sock.sendall(b'\xde\xad\xbe\xef') sock.close()
これで、ステージ 5までは突破できた。最後のsystemが実行しても何も吐き出さないので困った。ここで、chdirで/tmpに移行したことがダメだということがわかった。inputプログラムを実行後はcwdを動かせないので、どうやってもflagファイルがあるディレクトリに戻れず、最後のsystemが実行されても何も起こらない。
調べたらここはシンボリックリンクを使うみたいだった。ファイルが保存できるのは、/tmp以下なので、ここで、”実行する場所は/tmp以下でやら”なければならないことがわかった。シンボリックリンクを作成することで実行したディレクトリで、flagを開くというギミックだった。
以下、/tmp内に作った作業用ディレクトリで実行するスクリプト（解答）
import os import subprocess import socket import time def main(): os.system("ln -s /home/input2/flag flag") os.putenv("\xde\xad\xbe\xef", "\xca\xfe\xba\xbe") args = ["0"] * 99 args[ord("A")-1] = "" args[ord("B")-1] = "\x20\x0a\x0d" stdinr, stdinw = os.pipe() stderrr, stderrw = os.pipe() os.write(stdinw, "\x00\x0a\x00\xff") os.write(stderrw, "\x00\x0a\x02\xff") f = open("\x0a","w") f.write("\x00\x00\x00\x00") f.close() args[ord("C")-1] = '1234' subprocess.Popen(["/home/input2/input"]+args,stdin=stdinr,stderr=stderrr) time.sleep(1) sock = socket.socket(family=socket.AF_INET,type=socket.SOCK_STREAM) sock.connect(('127.0.0.1',1234)) sock.sendall(b'\xde\xad\xbe\xef') sock.close() if __name__ == '__main__': main()
サーバーのポートは適当に指定。最初65432でやったら別のでやってねって言われた。何回か適当な数入れてこれが大丈夫だった。
C++の参照型について学んだ
llvmのチュートリアル、kaleidoscopeをやっていて、何だろうと思ったので調べた。
int a=100;
int &b=a;
b = 99;
printf("%d,%d\n",a,b);
これをやると両方99になるというやつ。
#include <cstdio>
using namespace std;
int main(){
int a = 100;
int &b = a;
printf("%p,%p\n",&a,&b);
return 0;
}
アドレスを表示してみる。
% ./a.out (git)-[master] 0x7ffeebeba978,0x7ffeebeba978
同じだ。 これはポインタで間接参照演算子*を使えばできるやつだなって最初思った。 javaとかのオブジェクトは参照型だから関数とかに渡した時に呼び出し先で変えると呼び出し元も変わってるってやつだよね。
基本C言語がメインで書いてたしめちゃめちゃ不思議な感覚。 pythonは全てオブジェクトとして扱うけど、基本的なやつは、参照型じゃないのよね
>>> a = 100 >>> b = a >>> b = 99 >>> print(a,b) 100 99 >>> a = [1,2,3,4] >>> b = a >>> b[1]=4 >>> a [1, 4, 3, 4]
よく考えたらこれも不思議だよねって ちょっと不思議だなと思いつつちょっと便利だなとも思ったえぬわいであった...
ルックアヘッドキャリー加算器
vhdlで2bitのルックアヘッドキャリー加算器を書いてみた。
このくらいじゃ威力はないけど、桁が上がるにつれて強力になる回路。
ウィキがわかりやすい。
単純に普通の加算器のキャリー部分を別回路にしたもの。
x桁目から x+1 桁目にいく(小さい桁から数えて)キャリーをとすると、
次の桁のキャリーは、感覚的に
そのまた次のは
これを展開すれば良いという話になるんだと思う。そうすると、2段になる。
これを踏まえて2bitの加算器の普通のとルックアヘッド型のvhdlのコードを比較してみた。
以下コード
library IEEE; use IEEE.std_logic_1164.all; entity ADDER_2BIT is port (A,B: in std_logic_vector(1 downto 0); S: out std_logic_vector(1 downto 0); OVERFLOW: out std_logic); end ADDER_2BIT; architecture RTL of ADDER_2BIT is component HARF_ADDER port(A,B:in std_logic; S,CARRY:out std_logic); end component; component FULL_ADDER port(A,B,PRECARRY: in std_logic; S,CARRY: out std_logic); end component; signal TMP_CARRY: std_logic; begin FIRST_ADDER: HARF_ADDER port map(A=>A(0),B=>B(0),S=>S(0),CARRY=>TMP_CARRY); SECOND_ADDER: FULL_ADDER port map(A=>A(1),B=>B(1),S=>S(1),PRECARRY=>TMP_CARRY,CARRY=>OVERFLOW); end RTL;
library IEEE; use IEEE.std_logic_1164.all; entity LOOK_AHEAD_2BIT_ADDER is port(A,B: in std_logic_vector(1 downto 0); S: out std_logic_vector(1 downto 0); OVERFLOW: out std_logic); end LOOK_AHEAD_2BIT_ADDER; architecture RTL of LOOK_AHEAD_2BIT_ADDER is component LOOK_AHEAD_HARF port(A,B: in std_logic; S: out std_logic); end component; component FULL_ADDER port(A,B,PRECARRY: in std_logic; S,CARRY: out std_logic); end component; signal TMP_CARRY: std_logic; begin FIRST_ADDER: LOOK_AHEAD_HARF port map(A(0),B(0),S(0)); SECOND_ADDER: FULL_ADDER port map(A(1),B(1),TMP_CARRY,S(1),OVERFLOW); TMP_CARRY <= A(0) and B(0); end RTL;
で、テストベンチ。 実時間を計測できないからなんとも言えないけど、今回はとりあえず、同じ結果になればいいかなという軽いノリ。
書いて見て、ルックアヘッド型の半加算器、全加算器が必要だってことがわかった。2bitだと、ルックアヘッド型の全加算器は必要ないけど、3bit以上になると使うはず。 ルックアップ型の加算器で使うのは、キャリーをただ省いただけのもの。だけど、普通のタイプを流用した場合、そのキャリーはどこにつなげるのという話になると思う。ここからは推測だけど、適当なところにつなぐんじゃないか。浮かせることは可能なんだろうか？ディスクリートのICを触ると、基本浮かせるのはよくないとされているので、つなぐんじゃないかなと思う。その際に使わないくせに電力を食うわけだし、やっぱ外すのがいいんだと思う。
esp32で2.8 Inch TFT液晶とUSB HOST LIB使った
サンプルをくっつけた感じが強いのですが、使いました。
有線のキーボードを使って、TFTディスプレイに入力したキーを表示させました。
使用機器
配線
USBシールドはここから抜粋。 GPIO5 : SS, GPIO17 : INT, GPIO18 : SCK, GPIO19 : MISO, GPIO23 : MOSI
USBシールドの配線は上記のサイトで確認。ボードの裏を見るとMISOとCLKが逆に書かれているので注意する。困ったら、arduinoボードの配線を見て確認すれば良い。arduino用にシールドのピンが配置されているため。
TFTの配線はこの方を参考に
2.4 Inch TFT Display For ESP32macsbug.wordpress.com
たまたまピン配置が被らなかったので、これでいけた。変える場合はUSBホストの方はソースコードを直接いじることになる。tftの方はオブジェクトを生成するときに設定できる。
ソースコード
僕はusb hostとtftのライブラリはgithubから取ってきた。
GitHub - adafruit/Adafruit_ILI9341: Library for Adafruit ILI9341 displays
GitHub - felis/USB_Host_Shield_2.0: Revision 2.0 of USB Host Library for Arduino.
ライブラリーはここからcloneして、arduinoのlibrariesフォルダに入れればおk。
あとはこれらをまとめればいい。C++はあんまやったことないので、変なところは目をつむって欲しいですが。
// SPI
#include <SPI.h>
// TFT display module
#include <gfxfont.h>
#include <Adafruit_GFX.h>
#include <Adafruit_SPITFT.h>
#include <Adafruit_SPITFT_Macros.h>
#include <Adafruit_GFX.h>
#include <Adafruit_ILI9341.h>
// USB HOST
#include <hidboot.h>
#include <usbhub.h>
class KbdRptParser : public KeyboardReportParser
{
public:
Adafruit_ILI9341 *tft;
void PrintKey(uint8_t mod, uint8_t key);
protected:
void OnControlKeysChanged(uint8_t before, uint8_t after);
void OnKeyDown (uint8_t mod, uint8_t key);
void OnKeyUp (uint8_t mod, uint8_t key);
void OnKeyPressed(uint8_t key);
};
void KbdRptParser::PrintKey(uint8_t m, uint8_t key)
{
}
void KbdRptParser::OnControlKeysChanged(uint8_t before, uint8_t after){
}
void KbdRptParser::OnKeyDown(uint8_t mod, uint8_t key)
{
if(key==0x28){
(*(this->tft)).println("");
}else{
(*(this->tft)).print((char)OemToAscii(mod,key));
}
}
void KbdRptParser::OnKeyUp(uint8_t mod, uint8_t key){
}
void KbdRptParser::OnKeyPressed(uint8_t key){
}
USB Usb;
HIDBoot<USB_HID_PROTOCOL_KEYBOARD> HidKeyboard(&Usb);
KbdRptParser Prs;
Adafruit_ILI9341 tft = Adafruit_ILI9341(13,14,27,26,12,25);
void setup() {
Serial.begin(115200);
tft.begin();
tft.fillScreen(ILI9341_BLACK);
yield();
tft.setCursor(0,0);
tft.setTextColor(ILI9341_GREEN);
tft.setTextSize(2);
tft.setRotation(2);
tft.println("Initialize USB...");
delay(1000);
if(Usb.Init() == -1){
tft.println("USB initialization failed.");
}else{
tft.println("OK");
}
tft.println("Setting...");
HidKeyboard.SetReportParser(0,&Prs);
Prs.tft = &tft;
delay(500);
tft.println("OK");
tft.setTextColor(ILI9341_WHITE);
tft.println("Input Any String:");
}
void loop() {
Usb.Task();
}
こんな感じになる
ただし、今は改行しか実装してない。 横の自動改行はデフォルトで入っているので、あとは、縦のスクロールとフォントをなんとかしたいなと思ってる。 C++勉強しないとなぁという気持ちになっている。タッチ使えるんだけど、個人的にタッチは好きじゃないので、ジョイスティックとバイブレーションをUIとして実装したい。
二分探索使える？
ろくに大学の授業で書いてないので、使えるかというとぶっちゃけ使えなかったんだが、今完全に理解した（ネタ）
最近、競プロでよく使うので、簡単なモジュールを書いた。
のあれ
2分探索を使う場所について
たとえば、より大きい最小の整数を求めるときとか、ソートされた配列内においてある数Xより小さい最大の数がどこにあるか知りたいときとか。割と使う場面があるんだよって学校でのくそつまんねぇ探索用途以外にもたくさんあるんだよってあの時の自分に教えてあげたい...
lower_boundとupper_bound
C++にはlower_boundとupper_boundというサクッと使えるいい感じのライブラリがある。pythonには、検索かけた感じなかった。
lower_boundというのは、訳すと下界、upper_boundは上界。数学の用語。
イメージとしてlower_boundは、ある条件を満たす配列の一番下の要素。upper_boundは、ある条件を満たすものの一番上の要素。
実装 兼 テスト
以下、蟻本をベースにした実装。
""" bound.py for util binary search """ def ge(k,array,ind): return array[ind]>=k def lower_bound(k, array, func=ge): """ k 以上を満たす最小のインデックスを返す もしなかったら要素数を返す """ lb=-1 ub=len(array) while ub-lb>1: mid = (lb+ub)//2 if func(k,array,mid): ub=mid else: lb=mid return ub def lt(k,array,ind): return array[ind]<k def upper_bound(k, array, func=lt): """ k 未満を満たす最大のインデックスを返す もしなかったら-1を返す """ lb=-1 ub=len(array) while ub-lb>1: mid = (lb+ub)//2 if func(k,array,mid): lb=mid else: ub=mid return ub-1
以下、簡単なテスト
""" test_bound.py for tesging bound.py """ from bound import lower_bound, upper_bound import unittest class BoundTest(unittest.TestCase): def setUp(self): self.normal_array = [1,2,3,4,5,6,7] def test_lower(self): l = lower_bound(5,self.normal_array) self.assertEqual(l,4) def test_none_lower(self): l = lower_bound(8,self.normal_array) self.assertEqual(l,len(self.normal_array)) def test_upper(self): u = upper_bound(5,self.normal_array) self.assertEqual(u,3) def test_none_upper(self): u = upper_bound(-1,self.normal_array) self.assertEqual(u,-1) def test_func_lower(self): l = lower_bound(34, [1,2,3,4,5,6], func=lambda k,array,ind: k<=2**array[ind]) self.assertEqual(l,5) def test_func_upper(self): u = upper_bound(29, [1,2,3,4,5], func=lambda k,array,ind: 3**array[ind]<k) self.assertEqual(u, 2)
% python -m unittest test_bound.py ...... ---------------------------------------------------------------------- Ran 6 tests in 0.001s OK
うむ。 今日というか昨日esp32で2.8インチ液晶モジュールのテストをしたんだけど、思ってたより達成感というか成長感がなくてブログに書くのはやめることにした。こういうこともあるんだなぁという気持ち。
VHDLのstd_logic_vectorとloopの変換
結論から書きます。この記事を書くことになった経緯や思いは後半部分に書こうと思います。
loop 変数からstd_logic_vectorの変換方法
一度、unsignedに直して、std_logic_vectorに入れる。 ghdlでコンパイルしました。 断片的にコードを書き写すのが難しい言語なので、簡単な加算器のテストベンチを貼ります。
library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all; entity ADDER_2BIT_TEST is end ADDER_2BIT_TEST; architecture RTL of ADDER_2BIT_TEST is component ADDER_2BIT port(A,B: in std_logic_vector(1 downto 0); S: out std_logic_vector(1 downto 0); OVERFLOW: out std_logic); end component; constant STEP: Time := 100 ns; signal A,B,S: std_logic_vector(1 downto 0); signal OVERFLOW: std_logic; begin U0: ADDER_2BIT port map(A,B,S,OVERFLOW); process begin for I in 0 to 3 loop for J in 0 to 3 loop A <= std_logic_vector(to_unsigned(I,2)); B <= std_logic_vector(to_unsigned(J,2)); wait for STEP; end loop; end loop; wait; end process; end RTL;
このprocess文のところ。unsignedに直して、std_logic_vectorに直すとイける。 adaの型変換の話がまだ掴めていないのでなんとも言えないです。 強い静的型付け言語感をひしひしと感じています。オブジェクト指向らしいのですが、std_logic_vector()がキャストで、to_unsignedでunsignedのオブジェクトを生成してるらしいです。unsignedがわかって、その後std_logic_vector(unsigned(I,2))ってコンストラクタっぽく使ってたらずっとエラー出てました。 vhdl std_logic_vector loop で検索してたらあんまいい情報が出なくて、これ書いてる途中に std_logic_vector unsignedで検索したら一発だった...さっきの猛烈に検索してた時間はなんだったのか...
まぁ、新しいこと学べたのでよしとします。
経緯
学校でVHDLをやっていまして、これからFPGAのボード触るらしいです。個人的に前からFPGAは調べてた割には、環境が統一、一貫されてなさすぎて、調べて終わりみたいな感じになってたので嬉しいです。最初の方でコリコリ書いてたら少し面白みが出てきてしまったので、やる気がモリモリなのです。
教科書もなかなかわかりやすいと思っています。誤字は少し多いですけど。後、v08に対応してないみたいですね。これを調べたそもそものきっかけがuse ieee.std_logic_arith.all;だったせいなんですよね。ghdlのライブラリに標準的に備わってなくて悲しかったです。わかりやすいと思うんだけどなぁ。残念。CPU周りは面白いので、これを機にadaとヘネパタよく読みたいですね。 CPU作りたみが深いですね。4 bitのCPUの作りかたの本はだいぶ有名なので、そっちを先に読もうかな。まぁ結果はともかく色々触ってみたいですね。
ところで、カテゴリーを追加してみました。目的は毎日の変化（成長）だけども目標はそれぞれのカテゴリーで50項目ぐらい作りたいです。1 週間にそれぞれ 1 記事書けば50週...w まぁそんな冗談は置いといて、地道にやっていきたいですね。やっとやりたいことができるモチベーションになってきたのに、時間がないんですよね。これが人生というものなのでしょうか。少しずつでもやっていきたいです（強い意志）
