几个概念

• track：sample的集合，表示一个视频或音频序列。
• hint track：不包含媒体数据，包含了一些将其他数据track打包成流媒体的指示信息。
• sample：一帧视频或一组连续视频帧，或一段连续的压缩音频，或定义一个或多个流媒体包的格式。
• sample table：指明sample时序和物理布局的表。
• chunk：一个track中几个sample组成的单元。

MP4 file is box/atom based.

• box header
  • 统一指明box的大小和类型
• box body
  • 根据类型有不同的意义和格式。

file type box (ftyp)

只有1个，并只能包含在文件层，不能被其他box包含，该box应该放在文件的最开始。

• 4B：box size
• 4B: box type, 'ftyp'
• 4B: major brand
• 4B: minor version
• 8B: compatible brands
• 共24字节

movie box (moov)

container box，包含文件媒体的metadata信息，只有1个，并只能包含在文件层。
一般情况下，moov中会包含一个mvhd和若干个trak。

movie header box (mvhd)

• 4B: box size
• 4B: box type, 'mvhd'
• 1B: box version, 一般为0
• 3B: flags
• 4B: creation time
• 4B: modification time
• 4B: time scale, 一秒时间内的刻度值
• 4B: duration, duration/time scale
• 4B: rate, 推荐播放速率
• 2B: volume, 1.0表示最大音量
• 10B: reserved
• 36B: matrix, 视频变换矩阵
• 24B: pre-defined
• 4B: next track id, 下一个track使用的id号
• 共120个字节

track box (trak)

container box，包含了媒体数据的引用和描述。
trak必须包含一个tkhd和一个mdia，此外还有很多可选的box。

track header box (tkhd)

• 4B: box size
• 4B: box type, 'tkhd'
• 1B: box version, 一般为0
• 3B: flags， 一般该值为7
  • 0x000001, track_enabled, 否则track不能被播放
  • 0x000002, track_in_movie, 表示该track在播放中被引用
  • 0x000004, track_in_preview, 表示该track在预览是被引用
• 4B: creation time
• 4B: modification time
• 4B: track id, 不能重复，且不能为0
• 4B: reserved
• 4B: duration
• 8B: reserved
• 2B: layer, 视频层，默认为0，值小的在上层
• 2B: alternate group, track 分组信息
• 2B: volume, 如果为音频track，1.0表示最大音量，否则为0
• 2B: reserved
• 36B: matrix, 视频变换矩阵
• 4B: width
• 4B: height
• 共92个字节

media box (mdia)

container box，其子box结构和种类比较复杂。
一般来说，mdia包含一个mdhd，一个hdlr和一个minf。

media header box (mdhd)

• 4B: box size
• 4B: box type, 'mdhd'
• 1B: box version, 一般为0
• 3B: flags
• 4B: creation time
• 4B: modification time
• 4B: time scale
• 4B: duration
• 2B: language, 媒体语言码
• 2B: pre-defined
• 共16个字节

handler reference box (hdlr)

解释了媒体的播放过程信息，该box也可以包含在meta box(meta)中。

• 4B: box size
• 4B: box type, 'hdlr'
• 1B: version
• 3B: flags
• 4B: pre-defined
• 4B: handler type, 在midia box中该值为4个字符
  • vide: video track
  • soun: audio track
  • hint: hint track
• 12B: reserved
• 不定: name, track type name, 以'\0'结尾的字符串

media information box (minf)

container box，存储了解释track媒体数据的handler-spcific信息，media handler用这些信息将媒体时间映射到媒体数据并进行处理。
一般情况下，minf包含一个header box，一个dinf和一个stbl，其中header box根据track type(media handler type)分为vmhd，smhd，hmhd和nmhd。

media information header box (vmhd, smhd, hmhd, nmhd)

1. video media header box (vmhd)

• 4B: box size
• 4B: box type, 'vmhd'
• 1B: version, 一般为0
• 3B: flags
• 4B: graphics mode, 视频合成模式
• 6B: opcolor, red/green/blue
• 共22个字节

2. sound media header box (smhd)

• 4B: box size
• 4B: box type, 'smhd'
• 1B: version， 一般为0
• 3B: flags
• 2B: balance, 立体声平衡，一般为0
• 2B: reserved
• 共16个字节

3. hint media header box (hmhd)
4. null media header box (nmhd)

data information box (dinf)

container box，解释如何定位媒体信息。
一般情况下，dinf包含一个dref，dref下会包含若干个url或urn，这些box组成一个表，用来定位track数据。

1. data reference box (dref)

• 4B: box size
• 4B: box type, 'dref'
• 1B: version
• 3B: flags
• 4B: entry count, url/urn表的元素个数
• 不定: url/urn列表

sample table box (stbl)

container box，包含了关于track中sample所有时间和位置信息，以及sample的编解码等信息。利用这个表，可以解释sample的时序，类型，大小以及在各自存储容器中的位置。

1. sample description box (stsd)
   必不可少，包含视频的编码类型，宽度，报读，音频的声道，采样等信息。
2. time to sample box (stts)
   存储了sample的duration，描述了sample时序的映射方法，通过它可以找到任何时间的sample。
3. sample size box (stsz)
   定义了每个sample的大小，包含了媒体中全部sample的数据和一张给出每个sample大小的表，这个表体积比较大。
4. sample to chunk box (stsc)
   存储了sample和chunk的映射关系，查该表可以找到包含指定sample的chunk，从而找到该sample。
5. sync sample box (stss)
   确定media中的关键帧，包含了一个sample序号表，严格按序号排列，说明了哪一个sample是关键帧，如果没有该表，说明每一个sample都是一个关键帧。
6. chunk offset box (stco)
   定义了每个chunk在媒体中的位置，该位置是相对整个文件的，因此，如果前面的box有了任何改变，该表需要重新建立。

media data box (mdat)

存储媒体数据。

以后就在这里写博客吧，:cat: 喵～～～

Emoji表情

将对应emoji表情的符号码复制后输入你的markdown文本即可显示emoji表情。
如:blush:，显示为:blush:

人物

syntax	preview	syntax	preview	syntax	preview
:bowtie:		:smile:	😄	:laughing:	😆
:blush:	😊	:smiley:	😃	:relaxed:	☺️
:smirk:	😏	:heart_eyes:	😍	:kissing_heart:	😘
:kissing_closed_eyes:	😚	:flushed:	😳	:relieved:	😌
:satisfied:	😆	:grin:	😁	:wink:	😉
:stuck_out_tongue_winking_eye:	😜	:stuck_out_tongue_closed_eyes:	😝	:grinning:	😀
:kissing:	😗	:kissing_smiling_eyes:	😙	:stuck_out_tongue:	😛
:sleeping:	😴	:worried:	😟	:frowning:	😦
:anguished:	😧	:open_mouth:	😮	:grimacing:	😬
:confused:	😕	:hushed:	😯	:expressionless:	😑
:unamused:	😒	:sweat_smile:	😅	:sweat:	😓
:disappointed_relieved:	😥	:weary:	😩	:pensive:	😔
:disappointed:	😞	:confounded:	😖	:fearful:	😨
:cold_sweat:	😰	:persevere:	😣	:cry:	😢
:sob:	😭	:joy:	😂	:astonished:	😲
:scream:	😱	:neckbeard:		:tired_face:	😫
:angry:	😠	:rage:	😡	:triumph:	😤
:sleepy:	😪	:yum:	😋	:mask:	😷
:sunglasses:	😎	:dizzy_face:	😵	:imp:	👿
:smiling_imp:	😈	:neutral_face:	😐	:no_mouth:	😶
:innocent:	😇	:alien:	👽	:yellow_heart:	💛
:blue_heart:	💙	:purple_heart:	💜	:heart:	❤️
:green_heart:	💚	:broken_heart:	💔	:heartbeat:	💓
:heartpulse:	💗	:two_hearts:	💕	:revolving_hearts:	💞
:cupid:	💘	:sparkling_heart:	💖	:sparkles:	✨
:star:	⭐	:star2:	🌟	:dizzy:	💫
:boom:	💥	:collision:	💥	:anger:	💢
:exclamation:	❗	:question:	❓	:grey_exclamation:	❕
:grey_question:	❔	:zzz:	💤	:dash:	💨
:sweat_drops:	💦	:notes:	🎶	:musical_note:	🎵
:fire:	🔥	:hankey:	💩	:poop:	💩
::	💩	:+1:	👍	:thumbsup:	👍
:-1:	👎	:thumbsdown:	👎	:ok_hand:	👌
:punch:	👊	:facepunch:	👊	:fist:	✊
:v:	✌️	:wave:	👋	:hand:	✋
:raised_hand:	✋	:open_hands:	👐	:point_up:	☝️
:point_down:	👇	:point_left:	👈	:point_right:	👉
:raised_hands:	🙌	:pray:	🙏	:point_up_2:	👆
:clap:	👏	:muscle:	💪	:metal:	🤘
:fu:	🖕	:walking:	🚶	:runner:	🏃
:running:	🏃	:couple:	👫	:family:	👪
:two_men_holding_hands:	👬	:two_women_holding_hands:	👭	:dancer:	💃
:dancers:	👯	:ok_woman:	🙆‍♀️	:no_good:	🙅
:information_desk_person:	💁	:raising_hand:	🙋	:bride_with_veil:	👰‍♀️
:person_with_pouting_face:	:person_with_pouting_face:	:person_frowning:	:person_frowning:	:bow:	🙇
:couplekiss:	💏	:couple_with_heart:	💑	:massage:	💆
:haircut:	💇	:nail_care:	💅	:boy:	👦
:girl:	👧	:woman:	👩	:man:	👨
:baby:	👶	:older_woman:	👵	:older_man:	👴
:person_with_blond_hair:	:person_with_blond_hair:	:man_with_gua_pi_mao:	👲	:man_with_turban:	👳‍♂️
:construction_worker:	👷	:cop:	👮	:angel:	👼
:princess:	👸	:smiley_cat:	😺	:smile_cat:	😸
:heart_eyes_cat:	😻	:kissing_cat:	😽	:smirk_cat:	😼
:scream_cat:	🙀	:crying_cat_face:	😿	:joy_cat:	😹
:pouting_cat:	😾	:japanese_ogre:	👹	:japanese_goblin:	👺
:see_no_evil:	🙈	:hear_no_evil:	🙉	:speak_no_evil:	🙊
:guardsman:	💂‍♂️	:skull:	💀	:feet:	🐾
:lips:	👄	:kiss:	💋	:droplet:	💧
:ear:	👂	:eyes:	👀	:nose:	👃
:tongue:	👅	:love_letter:	💌	:bust_in_silhouette:	👤
:busts_in_silhouette:	👥	:speech_balloon:	💬	:thought_balloon:	💭
:feelsgood:		:finnadie:		:goberserk:
:godmode:		:hurtrealbad:		:rage1:
:rage2:		:rage3:		:rage4:
:suspect:		:trollface:

自然

syntax	preview	syntax	preview	syntax	preview
:sunny:	☀️	:umbrella:	☔	:cloud:	☁️
:snowflake:	❄️	:snowman:	⛄	:zap:	⚡
:cyclone:	🌀	:foggy:	🌁	:ocean:	🌊
:cat:	🐱	:dog:	🐶	:mouse:	🐭
:hamster:	🐹	:rabbit:	🐰	:wolf:	🐺
:frog:	🐸	:tiger:	🐯	:koala:	🐨
:bear:	🐻	:pig:	🐷	:pig_nose:	🐽
:cow:	🐮	:boar:	🐗	:monkey_face:	🐵
:monkey:	🐒	:horse:	🐴	:racehorse:	🐎
:camel:	🐫	:sheep:	🐑	:elephant:	🐘
:panda_face:	🐼	:snake:	🐍	:bird:	🐦
:baby_chick:	🐤	:hatched_chick:	🐥	:hatching_chick:	🐣
:chicken:	🐔	:penguin:	🐧	:turtle:	🐢
:bug:	🐛	:honeybee:	🐝	:ant:	🐜
:beetle:	🪲	:snail:	🐌	:octopus:	🐙
:tropical_fish:	🐠	:fish:	🐟	:whale:	🐳
:whale2:	🐋	:dolphin:	🐬	:cow2:	🐄
:ram:	🐏	:rat:	🐀	:water_buffalo:	🐃
:tiger2:	🐅	:rabbit2:	🐇	:dragon:	🐉
:goat:	🐐	:rooster:	🐓	:dog2:	🐕
:pig2:	🐖	:mouse2:	🐁	:ox:	🐂
:dragon_face:	🐲	:blowfish:	🐡	:crocodile:	🐊
:dromedary_camel:	🐪	:leopard:	🐆	:cat2:	🐈
:poodle:	🐩	:paw_prints:	🐾	:bouquet:	💐
:cherry_blossom:	🌸	:tulip:	🌷	:four_leaf_clover:	🍀
:rose:	🌹	:sunflower:	🌻	:hibiscus:	🌺
:maple_leaf:	🍁	:leaves:	🍃	:fallen_leaf:	🍂
:herb:	🌿	:mushroom:	🍄	:cactus:	🌵
:palm_tree:	🌴	:evergreen_tree:	🌲	:deciduous_tree:	🌳
:chestnut:	🌰	:seedling:	🌱	:blossom:	🌼
:ear_of_rice:	🌾	:shell:	🐚	:globe_with_meridians:	🌐
:sun_with_face:	🌞	:full_moon_with_face:	🌝	:new_moon_with_face:	🌚
:new_moon:	🌑	:waxing_crescent_moon:	🌒	:first_quarter_moon:	🌓
:full_moon:	🌕	:waning_gibbous_moon:	🌖	:last_quarter_moon:	🌗
:waning_crescent_moon:	🌘	:last_quarter_moon_with_face:	🌜	:first_quarter_moon_with_face:	🌛
:moon:	🌔	:earth_africa:	🌍	:earth_americas:	🌎
:earth_asia:	🌏	:volcano:	🌋	:milky_way:	🌌
:partly_sunny:	⛅	:octocat:		:squirrel:	:squirrel:
:waxing_gibbous_moon:	🌔

物体

地点

符号

syntax	preview	syntax	preview	syntax	preview
:one:	1️⃣	:two:	2️⃣	:three:	3️⃣
:four:	4️⃣	:five:	5️⃣	:six:	6️⃣
:seven:	7️⃣	:eight:	8️⃣	:nine:	9️⃣
:keycap_ten:	🔟	:1234:	🔢	:zero:	0️⃣
:hash:	#️⃣	:symbols:	🔣	:arrow_backward:	◀️
:arrow_down:	⬇️	:arrow_forward:	▶️	:arrow_left:	⬅️
:capital_abcd:	🔠	:abcd:	🔡	:abc:	🔤
:arrow_lower_left:	↙️	:arrow_lower_right:	↘️	:arrow_right:	➡️
:arrow_up:	⬆️	:arrow_upper_left:	↖️	:arrow_upper_right:	↗️
:arrow_double_down:	⏬	:arrow_double_up:	⏫	:arrow_down_small:	🔽
:arrow_heading_down:	⤵️	:arrow_heading_up:	⤴️	:leftwards_arrow_with_hook:	↩️
:arrow_right_hook:	↪️	:left_right_arrow:	↔️	:arrow_up_down:	↕️
:arrow_up_small:	🔼	:arrows_clockwise:	🔃	:arrows_counterclockwise:	🔄
:rewind:	⏪	:fast_forward:	⏩	:information_source:	ℹ️
:ok:	🆗	:twisted_rightwards_arrows:	🔀	:repeat:	🔁
:repeat_one:	🔂	:new:	🆕	:top:	🔝
:up:	🆙	:cool:	🆒	:free:	🆓
:ng:	🆖	:cinema:	🎦	:koko:	🈁
:signal_strength:	📶	:u5272:	🈹	:u5408:	🈴
:u55b6:	🈺	:u6307:	🈯	:u6708:	🈷️
:u6709:	🈶	:u6e80:	🈵	:u7121:	🈚
:u7533:	🈸	:u7a7a:	🈳	:u7981:	🈲
:sa:	🈂️	:restroom:	🚻	:mens:	🚹
:womens:	🚺	:baby_symbol:	🚼	:no_smoking:	🚭
:parking:	🅿️	:wheelchair:	♿	:metro:	🚇
:baggage_claim:	🛄	:accept:	🉑	:wc:	🚾
:potable_water:	🚰	:put_litter_in_its_place:	🚮	:secret:	㊙️
:congratulations:	㊗️	:m:	Ⓜ️	:passport_control:	🛂
:left_luggage:	🛅	:customs:	🛃	:ideograph_advantage:	🉐
:cl:	🆑	:sos:	🆘	:id:	🆔
:no_entry_sign:	🚫	:underage:	🔞	:no_mobile_phones:	📵
:do_not_litter:	🚯	:non-potable_water:	🚱	:no_bicycles:	🚳
:no_pedestrians:	🚷	:children_crossing:	🚸	:no_entry:	⛔
:eight_spoked_asterisk:	✳️	:eight_pointed_black_star:	✴️	:heart_decoration:	💟
:vs:	🆚	:vibration_mode:	📳	:mobile_phone_off:	📴
:chart:	💹	:currency_exchange:	💱	:aries:	♈
:taurus:	♉	:gemini:	♊	:cancer:	♋
:leo:	♌	:virgo:	♍	:libra:	♎
:scorpius:	♏	:sagittarius:	♐	:capricorn:	♑
:aquarius:	♒	:pisces:	♓	:ophiuchus:	⛎
:six_pointed_star:	🔯	:negative_squared_cross_mark:	❎	:a:	🅰️
:b:	🅱️	:ab:	🆎	:o2:	🅾️
:diamond_shape_with_a_dot_inside:	💠	:recycle:	♻️	:end:	🔚
:on:	🔛	:soon:	🔜	:clock1:	🕐
:clock130:	🕜	:clock10:	🕙	:clock1030:	🕥
:clock11:	🕚	:clock1130:	🕦	:clock12:	🕛
:clock1230:	🕧	:clock2:	🕑	:clock230:	🕝
:clock3:	🕒	:clock330:	🕞	:clock4:	🕓
:clock430:	🕟	:clock5:	🕔	:clock530:	🕠
:clock6:	🕕	:clock630:	🕡	:clock7:	🕖
:clock730:	🕢	:clock8:	🕗	:clock830:	🕣
:clock9:	🕘	:clock930:	🕤	:heavy_dollar_sign:	💲
:copyright:	©️	:registered:	®️	:tm:	™️
:x:	❌	:heavy_exclamation_mark:	❗	:bangbang:	‼️
:interrobang:	⁉️	:o:	⭕	:heavy_multiplication_x:	✖️
:heavy_plus_sign:	➕	:heavy_minus_sign:	➖	:heavy_division_sign:	➗
:white_flower:	💮	:100:	💯	:heavy_check_mark:	✔️
:ballot_box_with_check:	☑️	:radio_button:	🔘	:link:	🔗
:curly_loop:	➰	:wavy_dash:	〰️	:part_alternation_mark:	〽️
:trident:	🔱	:black_large_square:	⬛	:white_large_square:	⬜
:white_check_mark:	✅	:white_square_button:	🔳	:black_square_button:	🔲
:black_circle:	⚫	:white_circle:	⚪	:red_circle:	🔴
:large_blue_circle:	🔵	:large_blue_diamond:	🔷	:large_orange_diamond:	🔶
:small_blue_diamond:	🔹	:small_orange_diamond:	🔸	:small_red_triangle:	🔺
:small_red_triangle_down:	🔻	:shipit:

stealing from here

引言

有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。

（一）巴什博奕（Bash Game ）

只有一堆n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜。 显然，如果n=m+1 ，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。
因此我们发现了如何取胜的法则：如果 n= ( m+1 ) r+s ，（ r 为任意自然数， s≤m)，那么先取者要拿走 s 个物品，如果后取者拿走 k (≤m) 个，那么先取者再拿走 m+1-k 个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（ m+1 ）的倍数，就能最后获胜。
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100 者胜。

（二）威佐夫博奕（Wythoff Game ）

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（ak ， bk ）（ ak ≤ bk ,k=0 ， 1 ， 2 ， ...,n） 表示两堆物品的数量并称其为局势，如果甲面对（ 0 ， 0 ），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（ 0 ， 0 ）、（ 1 ， 2 ）、（ 3 ， 5 ）、（ 4 ， 7 ）、（ 6 ， 10 ）、（ 8 ， 13 ）、（ 9 ， 15 ）、（ 11 ， 18 ）、（ 12 ， 20 ）。
可以看出，a0=b0=0，ak 是未在前面出现过的最小自然数 , 而 bk= ak + k ，奇异局势有如下三条性质：

1. 任何自然数都包含在一个且仅有一个奇异局势中。
   由于ak 是未在前面出现过的最小自然数，所以有 ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质 1 成立。
2. 任意操作都可将奇异局势变为非奇异局势。
   事实上，若只改变奇异局势（ak ， bk ）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ ak ， bk ）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3. 采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a,b ），若 b = a ，则同时从两堆中取走 a 个物体，就变为了奇异局势（ 0 ， 0 ）；如果 a = ak ， b > bk ，那么，取走 b - bk 个物体，即变为奇异局势；如果 a = ak ， b < bk , 则同时从两堆中拿走 ak - ab - ak 个物体 , 变为奇异局势（ ab - ak , ab - ak+ b - ak ）；如果 a > ak ， b= ak + k, 则从第一堆中拿走多余的数量 a - ak 即可；如果 a < ak ， b= ak + k, 分两种情况，第一种， a=aj （ j < k ） , 从第二堆里面拿走 b - bj 即可；第二种， a=bj （ j < k ） , 从第二堆里面拿走 b - aj 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

那么任给一个局势（a ， b ），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k（ 1+√5 ） /2] ， bk= ak + k （ k=0 ， 1 ， 2 ， ...,n 方括号表示取整函数 )
奇妙的是其中出现了黄金分割数（1+√5 ） /2 = 1 。 618..., 因此 , 由 ak ， bk 组成的矩形近似为黄金矩形，由于 2/ （ 1+√5 ） = （ √5-1 ） /2 ，可以先求出 j=[a （ √5-1 ） /2] ，若 a=[j （ 1+√5 ） /2] ，那么 a = aj ， bj = aj + j ，若不等于，那么 a = aj+1 ， bj+1 = aj+1+ j + 1 ，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。

（三）尼姆博奕（Nimm Game ）

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况最有意思，它与二进制有密切关系，我们用（a ， b ， c ）表示某种局势，首先（ 0 ， 0 ， 0 ）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（ 0 ， n ， n ），只要与对手拿走一样多的物品，最后都将导致（ 0 ， 0 ， 0 ）。仔细分析一下，（ 1 ， 2 ， 3 ）也是奇异局势，无论对手如何拿，接下来都可以变为（ 0 ， n ， n ）的情形。

计算机算法里面有一种叫做按位模2 加，也叫做异或的运算，我们用符号（ + ）表示这种运算。这种运算和一般加法不同的一点是 1+1=0 。先看（ 1 ， 2 ， 3 ）的按位模 2 加的结果：

1 =二进制 01 
2 =二进制 10 
3 =二进制 11  （ + ） 
———————
0 =二进制 00  （注意不进位） 

对于奇异局势（0 ， n ， n ）也一样，结果也是 0 。
任何奇异局势（a ， b ， c ）都有 a （ + ） b （ + ） c =0 。
如果我们面对的是一个非奇异局势（a ， b ， c ），要如何变为奇异局势呢？假设 a < b< c, 我们只要将 c 变为 a （ + ） b, 即可 , 因为有如下的运算结果 : a （ + ） b （ + ） (a （ + ） b)=(a （ + ） a) （ + ） (b （ + ） b)=0 （ + ） 0=0 。要将 c 变为 a （ + ） b ，只要从 c 中减去 c- （ a （ + ） b ）即可。
例1 。（ 14 ， 21 ， 39 ）， 14 （ + ） 21=27 ， 39-27=12 ，所以从 39 中拿走 12 个物体即可达到奇异局势（ 14 ， 21 ， 27 ）。
例2 。（ 55 ， 81 ， 121 ）， 55 （ + ） 81=102 ， 121-102=19 ，所以从 121 中拿走 19 个物品就形成了奇异局势（ 55 ， 81 ， 102 ）。
例3 。（ 29 ， 45 ， 58 ）， 29 （ + ） 45=48 ， 58-48=10 ，从 58 中拿走 10 个，变为（ 29 ， 45 ， 48 ）。
例4 。我们来实际进行一盘比赛看看：
甲:(7,8,9)->(1,8,9) 奇异局势
乙:(1,8,9)->(1,8,4)
甲:(1,8,4)->(1,5,4) 奇异局势
乙:(1,5,4)->(1,4,4)
甲:(1,4,4)->(0,4,4) 奇异局势
乙:(0,4,4)->(0,4,2)
甲:(0.4,2)->(0,2,2) 奇异局势
乙:(0,2,2)->(0,2,1)
甲:(0,2,1)->(0,1,1) 奇异局势
乙:(0,1,1)->(0,1,0)
甲:(0,1,0)->(0,0,0) 奇异局势
甲胜。

Nim游戏

Nim游戏是博弈论中最经典的模型之一，它又有着十分简单的规则和无比优美的结论
　　Nim游戏是组合游戏 (Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称 ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而 言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的 任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据 这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。
　　通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
　 　这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然 后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同 样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已 经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。
　 　定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P- position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必 胜”。更严谨的定义是：

1. 无法进行任何移动的局面（也就是terminal position）是P-position；
2. 可以移动到P-position的局面是N-position；
3. 所有移动都导致N-position的局面是P-position。

　　按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。
　 　以Nim游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依 靠定义证明一下(3,3)是一个P是一个P是一个P-position。首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3) (1,3)(2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以 了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position（只 要找到一个是P-position的子局面就能说明是N-position）。(1,3)的后继中(1,1)是P-position（因为(1,1)的唯 一子局面(0,1)是N-position），所以(1,3)也是N-position。同样可以证明(2,3)是N-position。所以(3,3) 的所有子局面都是N-position，它就是P-position。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P- position当且仅当这两堆石子的数目相等”。
　　根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的 性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP 或者记忆化搜索的方法以提高效率。但问题是，利用这个算法，对于某个Nim游戏的局面(a1,a2,...,an)来说，要想判断它的性质以及找出必胜策 略，需要计算O(a1a2...*an)个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的 方法。
　　直接说结论好了。(Bouton's Theorem)对于一个Nim游戏的局面(a1,a2,...,an)，它是P- position当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道 理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按照两种position的证明来的。
　　根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题：

1. 这个判断将所有terminal position判为P-position；
2. 根据这个判断被判为N-position的局面一定可以移动到某个P-position；
3. 根据这个判断被判为P-position的局面无法移动到某个P-position。

　　第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。
　 　第二个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai'后满足 a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的 最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时 a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。
　　第三个命题，对于某个局面(a1,a2,...,an)，若 a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消 去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。
　　根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。

来自Wikipedia：

In computing, process substitution is a form of inter-process communication that allows the input or output of a command to appear as a file. The command is substituted in-line, where a file name would normally occur, by the command shell. This allows programs that normally only accept files to directly read from or write to another program.

语法格式：

<(<some command> <args>)

举例：

diff <(sort list-1.txt) <(sort list-2.txt)

flv 文件格式

flv header

9个字节：

• 8bit: 'F'
• 8bit: 'L'
• 8bit: 'V'
• 8bit: version
• 5bit: type flags reserved
• 1bit: type flags audio
• 1bit: type flags reserved, must be 0
• 1bit: type flags video
• 32bit: data offset

flv body

previous tag size0

• 32bit: always 0

tag1

tag header

11个字节：

• 8bit: tag type
  • 8: audio
  • 9: video
  • 18: meta
  • 其他：保留
• 24bit: data size
• 24bit: timestamp
  • 整数，单位毫秒
  • 对于脚本类tag，该值总为0
• 8bit: timestamp extended
  • 将时间戳扩展为4字节，代表高8位
• 24bit: stream id, always 0

tag data

• data
  • 根据tag type不同，分为音频tag，视频tag和script tag。

音频tag

第1字节为音频信息：

• 4bit: 音频格式
  • 2: mp3
  • 10: aac
  • 其他不解释了
• 2bit: 采样率
  • 0: 5.5khz
  • 1: 11khz
  • 2: 22khz
  • 3: 44khz，aac总是3
• 1bit: 采样长度
  • 0: 8bit
  • 1: 16bit，压缩过的音频都是16bit
• 1bit：音频类型
  • 0: sndMono
  • 1: sndStereo，aac总是1

其后为音频数据。如果AAC格式：

• 8bit：aac packet type
  • 0: aac sequence header
  • 1: aac raw
• 8nbit: aac data

视频tag

第1字节为视频信息：

• 4bit：帧类型

  • 1: keyframe(for avc, seekable)
  • 2: inter frame(for avc, non-seekable)
  • 3: disposable inter frame(H.263 only)
  • 4: generated frame(reserved for server only)
  • 5: video info/command frame

• 4bit: 编码id

  • 1: jpeg(currently unused)
  • 2: sorenson H.263
  • 3: screen video
  • 7: AVC

其后是视频数据。如果AVC格式：

• 8bit: avc packet type
  • 0: avc sequence header
  • 1: avc nalu
  • 2: avc end of sequence
• 24bit: composition time
• 8nbit: avc data

script tag

一般只有一个，是flv的第一个tag，用于存放flv文件的元信息。
所有脚本数据都是以数据类型+（数据长度）+数据的格式出现的，数据类型占1个字节，数据类型决定了是否包含数据长度字段，之后才是数据。

• 8bit: type
  • 0: number type
  • 1: boolean type
  • 2: string type
  • 3: object type
  • 4: movie clip type
  • 5: null type
  • 6: undefined type
  • 7: reference type
  • 8: ECMA array type
  • 10: strict array type
  • 11: date type
  • 12: long string type
• 32bit: ECMA array 长度，只有当type=8时存在
• nbit：script data value，根据不同type读取方式不同

如果类型为String，后面的2bytes为字符串的长度（Long String是4bytes），再后面才是字符串数据；
如果是Number类型，后面的8bytes为Double类型的数据；如果Boolean类型，后面1byte为Bool类型。

flv文件的脚本tag一般开头是0x02，表示String类型，后面的2bytes为字符串长度，一般是0x000a（“onMetaData”的长度），再后面就是字符串“onMetaData”。好像flv格式的文件都有onMetaData标记，在运行ActionScript的时候会用到它。后面跟的是0x08，表示ECMA Array类型，这个和Map比较相似，一个键跟着一个值。键都是String类型的，所以开头的0x02被省略了，直接跟着的是字符串的长度，然后是字符串，再是值的类型，也就是上面介绍的那些了。

关键帧信息也存储在script tag中。

'keyframes' object has 2 arrays: 'filepositions' and 'times'. 
Both arrays have the same number of elements, which is equal to the number of key frames in the FLV. 
Values in times array are in 'seconds'. Each correspond to the timestamp of the n'th key frame. 
Values in filepositions array are in 'bytes'. Each correspond to the fileposition of the n'th key frame video tag (which starts with byte tag type 9).

previous tag size1

• 32bit: size of previous tag, including its header

tag 2

...

tag n

...

previous tag sizen

• 32bit: size of previous tag, including its header