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 まぁそんな冗談は置いといて、地道にやっていきたいですね。やっとやりたいことができるモチベーションになってきたのに、時間がないんですよね。これが人生というものなのでしょうか。少しずつでもやっていきたいです（強い意志）
esp wroom 32を使い始めた
esp使い始めました。 先日、usb to serial変換モジュールが壊れたので、今回はesp wroom 32の大人しく開発キット買いました。
esp wroom 32 devkit C
秋月で売ってた esp-woom-32 dev kit cを買いました。 1500円くらい。micro usbを差すだけですぐ使える優れもの。正確にいうと差すだけでは使えない(os x) OS Xではドライバーを入れないと使えないです。
USB - UART ブリッジ VCP ドライバ|Silicon Labs
こっから落としてインストールする。
esp-wroom-32のflashバックアップ
esp-wroom-32にはSPI Flash と呼ばれる記憶領域がある。
https://www.espressif.com/sites/default/files/documentation/esp32_technical_reference_manual_en.pdf
このリファレンスのExternal Memoryの項を読むと書いてある. SPIを使用したFlashなのかな。とSPI SRAMも書いてある。Flashはread onlyでSRAMは読み書き可らしきことが書いてある。このFlashの方に色々書き込まれるみたいで、出荷時のバックアップをするときはこっから読みだして、保存すればいいんだと思う。4MB読み出せばいいことはわかったんだけど、なんで的な。これでわかった。
この方みたいに、esptoolsをcloneして読み出せばおk。パーティションとかどこに載ってるのかがまだわかんないけど、これで使う準備はできた。書き込み放題だ。
リファレンス読んだらだいぶできることあって面白そうだ。
余談
このdevkit cは普通のブレッドボード(真ん中が5行:5行で別れているやつ)を使うと片側1列しかなくて詰むんですよね。知らなくて買ったんですけど、家にあったブレッドボードを崩して使いました。ブレッドボードの裏側というか構造初めて見ました。
ちょっと時間がないのでここまでで。
ARC 103 D - Robot Arms
個人的に学ぶことが多かったのでメモメモ。
学んだこと
- 観察力の足りなさ
- 小さい例でもっと考える
- ちょっとずつ
- マンハッタン距離と45度回転
マンハッタン距離と45度回転
ちょっとここは数学的っぽいのでメモ。
マンハッタン距離を考える。
2次元の場合、
で定義される。例えば、原点から(1,2)までのマンハッタン距離は 3 とかね。
次に、適当にを考えるじゃん。
これから上下左右それぞれdだけ動いた点Bを考える。
上 :
下 :
右 :
左 :
こんな感じになる。
そして、45度回転させた座標系(u,v)を考える。つまり、(u, v) = (x+y, x-y) というような感じ。
正確には、を除いているわけだけど。
これが、ここで、u, v 上では、点Aは
になってるわけだ。
じゃあ、点Bは？
上 :
下 :
右 :
左 :
こんな感じになってるわけ。
ここで、
とすると、
点Bの u座標は , v座標は
といったように、u と v を分離することができたわけだ。これを用いるとそれぞれの座標u,vでdの足し引きだけで、次の点にいけるみたいだ。
これを用いたのが、解答
解答
def solve(xy): p = False if all([(x+y)%2==0 for x,y in xy]): p = True elif all([(x+y)%2==1 for x,y in xy]): pass else: print(-1) return m = [2**i for i in range(30,-1,-1)] if p: m.append(1) anses = [] for x,y in xy: usum, vsum = (0, 0) ans = [] u = x+y v = x-y anses.append(ans) for d in m: if usum <= u: usum += d if vsum <= v: vsum += d ans.append('R') else: vsum -= d ans.append('U') else: usum -= d if vsum <= v: vsum += d ans.append('D') else: vsum -= d ans.append('L') print(len(m)) print(" ".join([str(i) for i in m])) for a in anses: print("".join(a)) def main(): n = int(input()) xy = [] for i in range(n): xy.append([int(i) for i in input().split()]) solve(xy) if __name__ == '__main__': main()
ということになる。
参考
最近の 45 度回転事情 - Lilliput Steps
AtCoder ARC 103 D - Robot Arms (600 点) - けんちょんの競プロ精進記録
めちゃめちゃわかりやすかったです。
