C言語なら俺に聞け 153

2019/08/17(土) 23:02:42.00

C言語の話題のみ取り扱います C++の話題はC++スレへ
質問には最低限の情報(ソース/コンパイラ/OS)を付ける
数行で収まらないソースは以下を適当に使ってURLを晒す
https://paiza.io/
https://ideone.com/
http://codepad.org/

C11
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf

C99
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
http://kikakurui.com/x3/X3010-2003-01.html

C FAQ 日本語訳
http://www.kouno.jp/home/c_faq/

JPCERT C コーディングスタンダード
https://www.jpcert.or.jp/sc-rules/
-
VIPQ2_EXTDAT: checked:vvvvv:1000:512:----: EXT was configured
※前スレ
C言語なら俺に聞け 152
https://mevius.5ch.net/test/read.cgi/tech/1560763630/

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2019/11/29(金) 10:41:44.97

つかき君いるのかな

2019/11/29(金) 12:49:35.50

◯◯君が多過ぎて
だれかまとめろ

2019/11/29(金) 17:04:48.86

>>407
某ゲームで、ボスバトルまでの待ち時間が結構ありまして、そのちょっと前のタイミングを知るのに
ストップウォッチ兼タイマー ver 0.1 を愛用しております。自分で作ってもよかったのですが
蟻さんので必要十分だったのでありがたく使わせてもらっています。
ありがとうございました！

**蟻人間** ◆T6xkBnTXz7B0 (ｽﾌｯ Sdb2-cQuP) · 2019/11/29(金) 17:51:10.95

>>410
どういたしまして

**蟻人間** ◆T6xkBnTXz7B0 (ｽﾌｯ Sdb2-cQuP) · 2019/11/29(金) 19:33:21.96

ソースコード見たい？

**蟻人間** ◆T6xkBnTXz7B0 (ﾜｯﾁｮｲ 8101-Ql8R) · 2019/11/29(金) 19:39:20.32

https://github.com/katahiromz/mztimer
はいどうぞ。

**蟻人間** ◆T6xkBnTXz7B0 (ﾜｯﾁｮｲ 8101-Ql8R) · 2019/11/29(金) 19:41:30.08

昔の汚いソースだね。グローバル変数使いまくり。

2019/11/29(金) 19:44:15.31

パンツの中見せるの？

2019/11/29(金) 19:58:16.23

inline
が泣けるwww

2019/11/29(金) 20:52:16.59

>>413
TDM-GCCだとコンパイルできなかった

**蟻人間** ◆T6xkBnTXz7B0 (ｽﾌｯ Sdb2-cQuP) · 2019/11/29(金) 20:54:12.58

>>417
リソースがsjisだからUTF-8にして、コードページにちょっとしたトリックをするとビルドできるよ。

**蟻人間** ◆T6xkBnTXz7B0 (ﾜｯﾁｮｲ 8101-Ql8R) · 2019/11/29(金) 21:40:56.87

改良しました。

2019/11/29(金) 21:48:18.65

CMakeになっとるやんけ

2019/11/29(金) 23:02:39.40

>>419
蟻人間さんプルリク送っておいたからマージしてね

2019/11/29(金) 23:06:54.55

プルリク拒否られた・・・

2019/12/01(日) 19:27:28.70

大学の課題でフーリエ変換を利用した画像保存プログラムを作成せよっていう
課題が出ました…

もうお手上げです。助けてください

◆QZaw55cn4c (ﾜｯﾁｮｲ 7247-ddQu) · 2019/12/01(日) 19:32:56.92

>>423
宿題の文章を一文字も間違えずに正確に転載できる技術を持っているのなら
https://mevius.5ch.net/test/read.cgi/tech/1434079972/
で話の続きを聞く準備はあります、その出題自体はどこか変だとは思っていますが

2019/12/01(日) 19:35:57.20

>>423
画像の圧縮？

2019/12/01(日) 19:37:50.36

>>424
>>425
そうです。
実際に本気で組んだら何行くらいになるんでしょうか？
それだけでも目安を教えてほしいです。

例えば
木の絵をピクチャーボックスに描きました。
フーリエ保存してファイルを作成します。
ファイルを再現できました。
同じ絵です。
成功です。

こんな感じです。

2019/12/01(日) 19:38:04.98

大学名を教えてくれたらヒントくらいは出す

2019/12/01(日) 19:53:08.67

元の画像に戻ったら成功って事はフーリエ変換と逆変換かな？
フーリエ変換は外部ライブラリ使ってok？
okならOpenCV使えば良いんじゃね？

2019/12/01(日) 22:21:33.72

画像圧縮でフーリエ変換は罠だな、最初からDCT使って提出しようず

2019/12/01(日) 22:52:36.44

単機能だから、AWS Lambda で出来ないのか？
ライブラリを探すだけだろ

C/C++, PHP は、Lambdaには採用されていないけどw

2019/12/02(月) 00:41:46.52

>>426
何でも良いなら
1x8に区切って1次元でフーリエ変換して
適当にビット数を減らして保存

読み出してビット数を元にもどして逆フーリエ変換

フーリエ変換は
abcdefghhgfedcba
のようにすると
同じ結果が2個ずつ出るので
半分だけ保存する

2019/12/02(月) 00:42:32.51

さすがに1次元じゃ減点かなあ

2019/12/02(月) 00:46:10.70

8x8でやるなら
横でフーリエ変換した結果に対して縦でやればいい
16個のデータにするのは横とおなじ

2019/12/02(月) 00:48:32.83

フーリエ変換をDCTに変えて
ジグザグスキャンしてハフマン符号化すると
jpgになる

2019/12/02(月) 02:45:05.18

大学の課題と言うくらいだから画像云々はただの手段で目的はフーリエ変換というかFFTのアルゴリズムを実装できるか
というのが評価基準だと思う
間違って外部ライブラリを使ったり変に出題者の意図を捻じ曲げて解釈したりすれば減点される可能性高いから注意しろよ

2019/12/02(月) 09:05:35.78

>>435
みんな大学の課題という前提を忘れて実務的実用的な話になってるよね
フーリエ変換と逆変換をプログラムで実装できているかが採点基準であって
画像はバイナリデータがちゃんと元に戻っているか確認する手段にすぎないと思う

2019/12/02(月) 13:14:43.06

圧縮って書いてあるんだからバイナリ一致しなくてもいいのでは？
同じ絵っていうのはパッと見同じってことじゃなくて？

2019/12/02(月) 13:29:01.68

可逆圧縮か不可逆圧縮か

2019/12/02(月) 13:30:39.72

不可逆でフーリエ変換？

2019/12/02(月) 13:30:57.35

逆だ

可逆でフーリエ変換？

2019/12/02(月) 13:33:14.63

隣接ピクセル間隔より狭い高調波は不要だから有限の離散フーリエ変換でも
実質可逆とみていいんだよね？　（符号化による情報落ちを考慮しない話）

2019/12/02(月) 14:34:46.17

フーリエは本来可逆だ。

2019/12/02(月) 14:52:09.59

圧縮が目的でフーリエ変換するのに
何も情報を減らさずにそのまま戻してどうする？

2019/12/02(月) 14:53:09.69

>>441
心配しなくても
ナイキスト周波数を越える成分はフーリエ変換の結果には含まれない

2019/12/02(月) 14:56:19.28

>>423
>>426
離散コサイン変換じゃいかんのか

2019/12/02(月) 14:59:03.83

>>432
どうせ課題なんだしそこまで求めてないというか
もしすごいのが出来たら教授が自分の成果にして発表するんやろ

2019/12/02(月) 15:03:30.60

>>442
ほんそれ

ただし無限な

2019/12/02(月) 15:04:01.88

スゴイの出来たら、先に特許申請だな

2019/12/02(月) 15:06:19.88

講義での学習課題としては非圧縮でないと判定が面倒だな
単にデータを間引いただけなのか演算を間違っているのか確認に手間が掛かる
むしろ完全可逆で実装した方が採点する側としては分かりやすいだろう
出題者の意図はどこにあるか質問者は理解しているのだろうか？

2019/12/02(月) 15:16:11.81

なんで理解しなきゃいけねーの
そういう旨なら文章にハッキリ書いてくれねーと困るワケ
お気持ちを察せよ　なんてのが罷り通る案件なの？

2019/12/02(月) 15:18:11.07

「オメーの気持ちなんてしったこっちゃねー
　オレに分かるように話せ」
が今の潮流

分からないように反為さないヤツは無視していいし排除していい
なんつったってオレが理解出来ないヤツは何言ってるか分からないコミュニケーション不可能な敵に近いからな
気持ち悪いから排除してもいいし、何よりオレに理解されようと思ってない
だから排除していいでしょ

……という思考で動くのが現代の日本社会

2019/12/02(月) 15:21:55.25

いやクライアントの意向を無視して好き勝手やっていたら仕事干されるだろ

2019/12/02(月) 16:43:27.43

保存とは書かれているが圧縮とはどこにも書かれてない件

2019/12/02(月) 16:47:13.54

てか皆さん「フーリエ変換くらい当然知ってる」って雰囲気なのが凄いわ。

2019/12/02(月) 17:56:06.03

>>453
>>425,426

2019/12/02(月) 18:01:01.74

圧縮しないなら
保存でフーリエ変換使う意味がわからんがな

2019/12/02(月) 18:04:51.11

フーリエ変換そのものは理系の大学卒であれば誰でも知ってる
具体的な数値計算のアルゴリズムを知っているかはその人の専門分野による

2019/12/02(月) 18:35:35.76

理系でも生物系なら触りもせん

2019/12/02(月) 18:53:16.42

専門課程ではなくても一般教養の数学系の講義で学んでると思うけど

2019/12/02(月) 19:00:10.22

微積と線形代数ぐらいで触らんかったぞ
大学なんか講師次第だからなあ

2019/12/02(月) 19:09:01.78

文系だと無いと思うな
統計学や代数幾何、微積分
この辺まで

2019/12/02(月) 19:11:47.56

はるか前なので忘れたが、大学ではフーリエ級数って名前だった希ガス

2019/12/02(月) 19:12:24.77

理系の大学卒だが
フーリエ変換を大学で習った記憶はないなあ
覚えてないだけかな？

2019/12/02(月) 19:40:44.78

フーリエ変換はフーリエ級数展開の一般化
フーリエ級数展開の基本周期を無限大まで拡大すると周波数成分は離散から連続となる
要するに周波数成分を連続スペクトルとして扱うのがフーリエ変換

2019/12/03(火) 19:46:15.44

画像のフーリエ変換なんてどうやってやるんだ？って思ってググったら結構面白いな
ちょっと実装してみよう
https://algorithm.joho.info/image-processing/fourier-transform/

2019/12/03(火) 22:43:48.90

数学科院卒だがフーリエ変換には掠りもしてない
工学部の一部しか触ってないだろう

2019/12/04(水) 02:04:25.88

数学的には解析学の領域
どちらかといえば数学と物理の境界
電気工学や情報工学では必須
https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

2019/12/04(水) 02:24:25.40

工学部では厳密な理論よりも応用が重要なので表面的な触りだけで深入りはしない
厳密な議論はやはり数学者の分野だと思う

2019/12/04(水) 09:27:46.76

画像処理はOpenCVとかで済ましちゃうから細かい数式は気にしない

2019/12/04(水) 09:38:25.43

それには同意
フーリエ変換の利用にはFFTの概要だけ理解していれば十分
ただ数学の専門家が掠りもしてないというのは如何なものかとは思う

2019/12/04(水) 10:58:24.04

Wikipedia繋がりでFFTのリンク開いてみるとVisualBasicでの実装例が掲載されてるね
https://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

2019/12/04(水) 13:12:26.50

>>468
数学的にはとっくの昔に解決してるから
あとは工学系の仕事

2019/12/04(水) 13:15:06.38

>>470
応用数学とかそういう分野ならまだしも
純粋な数学者はそんなことには興味がない

2019/12/04(水) 13:17:30.35

FFTはアルゴリズムの名前

2019/12/04(水) 13:33:37.43

ラプラス変換やz変換あたりだと完全に工学分野だけどフーリエ変換くらい汎用なものは数学分野でも活用されてると思うけどね
フーリエ級数はローラン級数などと同じ複素解析の基本的な考え方でしょ
べきに展開するか指数に展開するかの違いくらいのもの

2019/12/04(水) 13:59:41.66

>>475
>>472

2019/12/04(水) 14:02:42.65

無理を言ってはいけない
数学者には楽器は作れても名曲を作る事はできない

2019/12/04(水) 15:03:29.21

名曲を作るのは数学者でも物理学者でも工学博士でもない
発明家や企業だ

2019/12/04(水) 21:02:14.66

沖縄音階は適当にランダムに音出しても曲に聞こえちゃうけどな

2019/12/04(水) 22:00:13.57

>>479
それは沖縄音階に馴染みがないから、沖縄音階が使われているだけで沖縄っぽいと感じてるだけなんじゃないかな？
沖縄の人からしたら、そんなデタラメでは曲として成り立ってないと思わないのかな。

2019/12/05(木) 00:53:08.83

そういった抽象的な感覚を数値化して扱うための手段がフーリエ解析やスペクトル解析と呼ばれる分野
音楽の音階(周波数)やリズム(時系列)を分解して客観的に評価するのが科学的なアプローチ

2019/12/05(木) 03:51:45.82

>>481
どちらかといえばウェーブレット解析の方が適しているような気がする
フーリエ変換では周波数特性を求める際に時間領域の情報は失われる
https://ja.wikipedia.org/wiki/%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%96%E3%83%AC%E3%83%83%E3%83%88%E5%A4%89%E6%8F%9B

プログラムで扱うなら離散ウェーブレット変換
https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%96%E3%83%AC%E3%83%83%E3%83%88%E5%A4%89%E6%8F%9B

2019/12/05(木) 07:07:45.12

確かにフーリエ解析では周波数成分の変化の時系列データを扱うのは難しい
少し浅はかだったなすまん
それにしても数学者が理論を確立して証明しそれをベースに開発が進むという典型例だな

2019/12/05(木) 11:04:28.35

200年くらいかかってるな
ベイズで100年ちょっとか

2019/12/05(木) 12:56:44.93

>>480
さあ？まあ、実際にやってみな。自分でピアノやオルガンのキーを沖縄音階で適当に押すだけでわかる。

2019/12/05(木) 13:09:00.01

自分で弾いたら曲になるように弾いちゃうからランダムじゃない
本当にランダムで弾いたら曲にならない

2019/12/05(木) 13:51:21.95

ム板ならそれらしくランダムに演奏するソフトうｐ汁
https://www.youtube.com/watch?v=5dsFqZf8owg

2019/12/05(木) 15:14:54.84

糞曲に興味はない

2019/12/05(木) 23:45:36.26

質問失礼いたします。
以下のpopcountは引数xを2進数で表したときの1の数を返す関数なのですが、
動作原理がよく理解できないため考え方のヒントなどをいただけないでしょうか。

int popcount(unsigned long long x)
{
　　x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
　　x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
　　return (int)(((x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f)) % 0xff);
}

以下のpopcount2は自分で作ったもので、これならうまくいくことは分かるのですが、
上のpopcountも本質的には同じことをやっていると考えていいものなのでしょうか。

int popcount2(unsigned long long x)
{
　　int n = 0;
　　for (int i = 0; i < 64; i++)
　　{
　　　　if ((x & 1ull << i) != 0ull)
　　　　{
　　　　　　n++;
　　　　}
　　}
　　return n;
}

どうぞよろしくお願いいたします。

2019/12/05(木) 23:51:53.81

https://ideone.com/8LfIh0
こんにちは。
ちょっと思いついたので、こういうコードを書いたのですが、
普段からreallocを使わないのでこのコードがあっているか解らないのです。
これで大丈夫ですか？

2019/12/06(金) 00:02:45.40

>>490
reallocが成功した場合古いポインタに対してfreeは呼ばなくていいと思いますよ。
reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、
freeを呼んでしまうとせっかくreallocした領域まで解放されてしまうかも。

2019/12/06(金) 00:04:45.19

>>491
了解です。ありがとうございました。

2019/12/06(金) 00:12:50.26

>>492
ちゃんとコードを読んだら↓の部分はケアされてましたね。失礼しました。
> reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、

ただ、reallocが成功したらfreeは呼ばなくていいのは間違いないと思います。

2019/12/06(金) 00:50:56.12

>>490 のreallocのコード返り値のポインタが不定を指しているので、使わないでください。
こっちを使ってください。
https://qiita.com/yakitori32/items/98256db666029fb5ebca

2019/12/06(金) 00:55:18.93

>>493
了解です。ありがとうございます。

2019/12/06(金) 01:07:01.79

>>489
超高速ビットカウント
でググって出てくるページでちゃんと解説してくれてる
この手のよく見るやつはちょっとググれば解説見つかる

何を本質と置くかによるけど両者はそもそもアルゴリズムが違うのでその観点からなら違う
どちらのコードも結果は同じでも前者のほうが圧倒的に処理速度が早い
ビット数などが必要になる処理では速度が重要になるケースも多々あるので結果が同じでも後者は使い物にならない場合もある

2019/12/06(金) 01:36:02.35

>>496
レスありがとうございます。紹介していただいた記事を読ませていただき、大変勉強になりました。

ただ、>>489 の場合だと「ビットカウントするデータ列がある程度長い場合」には
当てはまらないため記事の前半の内容がアルゴリズムの基本になるとか思うのですが、
私が理解した範囲で記事の内容を参考にして関数を作成しても以下のようにしかできませんでした。

int popcount(unsigned long long x)
{
　　x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
　　x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
　　x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
　　x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
　　x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
　　return (int)((x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff));
}

しかし >>489 の関数はこれを途中で打ち切って % 0xff をくっつけたような形になっており、
やはり完全な理解には至っていない状況です。
もし可能であれば、この部分についてもヒントをいただけると大変嬉しく思います。
たびたび申し訳ありませんが、どうぞよろしくお願いいたします。

2019/12/06(金) 04:41:11.15

>>497
64ビット長のビットカウントの最大値はたかだか64なので8ビット(最大255)で表現できる
一方、64ビットデータの分割統治による畳み込み計算は1回目で2ビット×32組、2回目で4ビット×16組、3回目で8ビット×8組の結果が得られる
ビット数を求めるだけなら3回目の結果が得られた時点で8ビットの最大数(255)で3回目の畳み込み結果の剰余を求めてやればそれぞれの組の重み(ビット数)が計算できる
(64を超えることはないことが明らかなので)

2019/12/06(金) 04:45:05.84

訂正
それぞれの組の重みの総計(ビット数)

2019/12/06(金) 05:11:25.02

>>498
わかりやすいご説明どうもありがとうございます！ほぼ理解できたと思います。
たとえば十進数の123を十進数文字の最大値9で割った余りは
1+2+3と等しくなりますが、これと同じ原理ということですよね？

ただよくよく考えてみると、そもそも十進数の各桁の合計を9で割った余りが
元の数を9で割った余りと等しくなることについても
お恥ずかしながら豆知識として知っているだけで原理を理解できていませんでした。
ただこれに関してはもはやC言語ではなく算数の問題なので、
その方面の解説サイトをググって勉強しようと思います。
なにはともあれ、回答してくださった皆様方、どうもありがとうございました。

>>495
読みやすい記事を提供してくださっているので、もう少しだけコメントさせてください。

現状だと、MemoryReAllocateを呼び出す側は関数の成否を確認するために
Mem->Memoryを覚えておく必要がありますので、MemoryReAllocateの引数に
参照渡しを使われるならMemoryReAllocateの戻り値はMomeryではなくて
成否を表すboolなどにされてはいかがでしょうか。

また、reallocは第一引数としてNULLを許容しているので
MemoryReAllocateは入力のMem->MemoryがNULLであっても
Mem->ElementSizeが正しい値であれば正常に動作しますが、
その一方でMemoryAllocateは失敗するとElementSizeがゼロの構造体を
返すので少しアンバランスかなと思いました。

あと、MemoryFreeがboolを返すのであれば、freeの前にNULLチェックを入れて
その結果をMemoryFreeの戻り値としてもいいかなと思いました。
（free関数自体はNULLを渡しても何もしないだけで問題は起こりませんが）

以上お目汚し失礼しました

2019/12/06(金) 05:15:04.10

1回進むごとに
2bitずつに区切って、1の数を各2bitに入れる
4bitずつに区切って、1の数を各4bitに入れる
8bitずつに区切って、1の数を各8bitに入れる
...

となるので
>>489だと各バイトの1の合計が、各バイトに入る

各バイトなので256バイトのテーブルを使う方法もある
チープなCPUだとこちらの方が速い

逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能

Icelake以降だとAVX512VBMIの命令を使って
超高速に64バイト分カウント出来る

2019/12/06(金) 05:24:05.53

>>500前半
なんか違う

10進数の各桁に関しては
1000a+100b+10c+d
=999a+99b+9c+a+b+c+d
=9(111a+11b+c)+(a+b+c+d)

これを2進数でやると
9のところが1になるからあまり意味がない

2019/12/06(金) 05:33:31.46

分割統治っていうより
レジスタ内の桁数を使ってSIMD演算してるって感じ

01020304 + 02040608

2桁ずつの4個の足し算になってるでしょ？

2019/12/06(金) 05:47:57.81

vpsrld
vpermb
vpermb
vpaddb

AVX512VBMIを使うと
レジスタに値がある状態で
4命令で64バイト分

2019/12/06(金) 05:56:22.53

>>501 >>504
レスありがとうございます。

> 各バイトなので256バイトのテーブルを使う方法もある
確かにある程度のビット幅ごとにテーブルを使って計算する方法は
シンプルですが効果が高そうですね。

> 逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能
> 4命令で64バイト分
勉強になります。本当に速さが必要ならCPU自体の理解から始めるべきなんですね。
このあたりのハードウェアの違いは標準ライブラリ関数が吸収してくれると最高なのですがｗ

>>502
10進数の話の数式どうもありがとうございます！大変勉強になりました。

そうすると、>>489 の popcount の最後にやっているのは
2進数というか0x100進数で、

0x1000000*a+0x10000f*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x01010x*a+0x0101*b+c)+(a+b+c+d)

ということになると思うのですがいかがでしょうか。

2019/12/06(金) 05:58:37.54

>>505 の数式が変でした。正しくは以下のとおりです。失礼しました。

0x1000000*a+0x10000*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x010101x*a+0x0101*b+c)+(a+b+c+d)

2019/12/06(金) 06:20:08.91

最後の % 0xff を見てなかった
なので各バイトの1の個数と勘違いしてました

>>506はその通り

%は、除算命令を使うと遅いので
コンパイラは
0x0101010101010101
との乗算とシフトに置き換えそうです

PCの64bit環境だとPOPCNT命令がそのまま1命令
Icelake以降だとVPOPCNTQで8個を1命令
で出来ます