Mercurial > hg > Papers > 2010 > kent-master
changeset 13:12cb508ee15d after-organizing
add slides for probation.
| author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 16 Feb 2010 14:48:06 +0900 |
| parents | 0f9a0ecc6afb |
| children | 064c4bd99db0 |
| files | Makefile paper/Makefile probation-slide/fact.cbc probation-slide/figures/call-return.png probation-slide/figures/continuation.png probation-slide/figures/gcc-flow.png probation-slide/figures/gcc-flow2.png probation-slide/figures/gcc-repository.png probation-slide/figures/tailcall.png probation-slide/figures/tailcallstack.png probation-slide/final-slide.css probation-slide/final-slide.html probation-slide/slidy.css probation-slide/slidy.js |
| diffstat | 14 files changed, 4995 insertions(+), 38 deletions(-) [+] |
line wrap: on
line diff
--- a/Makefile Tue Feb 16 14:43:52 2010 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,38 +0,0 @@ -MAKE=make -f Makefile -LATEX=platex -BIBTEX=jbibtex -MENDEX=mendex -DVIPS=pdvips -DVI2PDF=dvipdfmx -DVI2PDF_OPT=-f ptex-hiragino.map - -RM = rm -f - -TARGET=master_paper -PS_SUFFIX=.ps -PDF_SUFFIX=.pdf - -.SUFFIXES: .tex .dvi .pdf .toc - -default: $(TARGET).pdf - - -.dvi.pdf: - $(DVI2PDF) $(DVI2PDF_OPT) $^ - -.tex.dvi: - $(LATEX) $< - -bib: dvi - @echo "========== MAKE Bib file ($(MAIN_TARGET).dvi) ==========" - $(BIBTEX) $(MAIN_TARGET) - - -$(TARGET).dvi: abstract.tex introduction.tex cbc.tex gcc.tex implementation.tex evaluations.tex conclusion.tex thanx.tex bibliography.tex presentations.tex appendix.tex - -clean: - @echo "remove $(TARGET).{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out}" - $(RM) $(TARGET).{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out} - -veryclean: clean - find ./ -name \*~ -exec rm -f {} \;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/Makefile Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,38 @@ +MAKE=make -f Makefile +LATEX=platex +BIBTEX=jbibtex +MENDEX=mendex +DVIPS=pdvips +DVI2PDF=dvipdfmx +DVI2PDF_OPT=-f ptex-hiragino.map + +RM = rm -f + +TARGET=master_paper +PS_SUFFIX=.ps +PDF_SUFFIX=.pdf + +.SUFFIXES: .tex .dvi .pdf .toc + +default: $(TARGET).pdf + + +.dvi.pdf: + $(DVI2PDF) $(DVI2PDF_OPT) $^ + +.tex.dvi: + $(LATEX) $< + +bib: dvi + @echo "========== MAKE Bib file ($(MAIN_TARGET).dvi) ==========" + $(BIBTEX) $(MAIN_TARGET) + + +$(TARGET).dvi: abstract.tex introduction.tex cbc.tex gcc.tex implementation.tex evaluations.tex conclusion.tex thanx.tex bibliography.tex presentations.tex appendix.tex + +clean: + @echo "remove $(TARGET).{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out}" + $(RM) $(TARGET).{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out} + +veryclean: clean + find ./ -name \*~ -exec rm -f {} \;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/probation-slide/fact.cbc Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,29 @@ +#include<stdio.h> +#define code __code +#define __return _CbC_return +typedef code (*NEXT)(int,void*); + +int main(int argc, char **argv) ; +int factor(int x) ; +code factor0(int prod,int x,NEXT next) ; +code print_fact(int value) ; + + + + +int main(int argc, char **argv) { + int i,a; + i = atoi(argv[1]); + a = factor(i); + printf("%d! = %d\n", a); +} +int factor(int x) { + goto factor0(1, x, __return); +} +code factor0(int prod,int x,NEXT next) { + if (x >= 1) { + goto factor0(prod*x, x-1, next); + } else { + goto (*next)(prod,NULL); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/probation-slide/final-slide.css Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,175 @@ + +body { + font-family: "ＭＳ ゴシック"; + /*font-size: 14pt;*/ + /*background-color: #eeeeee;*/ + /*overflow: hidden;*/ + /*overflow: scroll;*/ +} +div.background { + height: 2.7em; + background-color: #009900; + background-color: gray; +} +div.header { + position: absolute; + z-index: 2; + left: 0; + right: 0; + top: 0; + bottom: auto; + width: 100%; + padding: 0; + margin: 0; + border: none; + + height: 0.2em; + /*background-color: #33ff00;*/ + background-color: #001111; + border-top: solid 1.8em #114444; + border-bottom: solid 0.7em #004444; +} +div.footer { + /*background-color: #33ff00;*/ + background-color: #001111; + position: fixed; + color: #eeeeff; + overflow: hidden; + + z-index: 50; + left: 0; + right: 0; + top: auto; + bottom: 0; + height: 1.4em; + margin: 0; + font-size: 80%; + font-weight: bold; + padding: 0.3em 0 0 1em; +} +div.slide { + margin: 0; + padding: 0; + /*background-color: #eeeeee;*/ +} +div.slide h1 { + position: relative; + background-color: #114444; + left: 0; + right: 0; + font-size: 140%; + + padding: 0.3em 1.1em 0 1em; + margin: 0; + margin-right: auto; + /*margin: 0 auto 1em 3em;*/ + /*width: -moz-fit-content;*/ + min-width: 60%; + + /* 高さは div.headerと調節 */ + height: 1.62em; + + color: white; + line-height: 1.1em; + +} +div.slide h2.uptitle { +} +#w3c-logo { + background-color: transparent; + width: auto; + height: auto; + margin-bottom: 1em; + overflow: hidden; + position: absolute; + bottom: 0; + right: 0; + display: none; +} +/* +#w3c-logo-fallback { +background-color: transparent; +width: 100%; +height: 100%; +margin: 0; +} + */ + +div.slide.top { +} +div.slide.top h1 { + font-size: 180%: + width: 80%; + height: auto; + margin: 3em auto 0; + padding: 0; + background: none; + color: black; +} + +div.slide.final h2 { + text-align: center; + vertical-align: center; + width: 80%; + margin: 7em auto 0; + padding: 0 + background: none: + color: black; +} + +p.subhead { +} + +ul li { + list-style-type: circle; + list-style-image: url("circle1.png"); + background: none; + padding-left: 0; + margin-left: 1em; +} +li li { + list-style-type: circle; + list-style-image: url(""); + background: none; +} + +.subtitle { + font-weight: bold; +} + +em { + color: brown; + font-style: normal; + font-weight: bold; +} + +em.weak { + color: black; + font-style: normal; + font-weight: bold; +} + +dfn { + color: brown; + font-style: normal; + font-weight: bold; +} + +pre { + font-style: normal; +} + + +dl > dt { + padding: 0; + margin: 0.3em 1em 0.3em; + width: 10%; + float: left; +} + +dl > dd { + padding: 0; + margin: 0.3em 1em 0.3em; + width: 70%; + float: left; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/probation-slide/final-slide.html Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,1487 @@ +<?xml version="1.0" encoding="utf-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja"> +<head> + <title>Continuation based C</title> + <meta name="copyright" content="Copyright © 2009 KSL: Yogi KENT" /> + <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> + <meta name="font-size-adjustment" content="1" /> + <link rel="stylesheet" href="slidy.css" + type="text/css" media="screen, projection, print" /> + <link rel="stylesheet" href="final-slide.css" + type="text/css" media="screen" /> + <!--link rel="stylesheet" href="../Slidy/w3c-blue2.css" + type="text/css" media="screen, projection, print" /--> + <style type="text/css"> + .right { + float: right; + width: 40%; + } + .left { + float: left; + width: 40%; + } + div.slide { + vertical-align: middle; + } + div.top h1 { + width: 70%; + padding: 0 1em 0; + text-align: center; + } + #frame { + position: fixed; + left: -1px; + top: -1px; + width: 800px; + height: 600px; + border: solid 1px red; + visibility: visible; + } + .speak { + + visibility: hidden; + + font-size: 80%; + line-height: 1.0; + position: fixed; + right: 0.5em; + bottom: 1.5em; + max-width: 60%; + background-color: green; + opacity: 0.90; + color: black; + -moz-border-radius: 8px; + -webkit-border-radius: 8px; + } + ul.narrow li { + margin-right: 0; + } + table { + border-collapse: collapse; + border: solid 1px black; + } + table td { + border: solid 1px black; + } + table th { + text-align: center; + border: solid 1px black; + } + </style> + <script src="slidy.js" + charset="utf-8" type="text/javascript"> + </script> + <script type="text/javascript"> + sizes = new Array("14pt", "15pt", "16pt", "17pt", "18pt", "19pt", "20pt", "21pt", "22pt","23pt", "24pt", "26pt", "28pt", "30pt", "32pt"); + sizeIndex = 1; + mouseClickEnabled = false; + </script> +</head> +<body> +<!-- this defines the slide background --> +<div id="frame"></div> + +<div class="background"> + <div class="header"> + <!-- sized and colored via CSS --> + </div> + + <!--img id="head-icon" alt="graphic with four colored squares" + src="../Slidy/icon-blue.png" /--> + + <div class="footer"> + <object id="w3c-logo" data="kent-logo2.svg" type="image/svg+xml" title="KENT logo"> + <a href="http://www.w3.org/"> + <img alt="W3C logo" id="w3c-logo-fallback" src="kent-logo2.png" /> + </a> + </object> + + <!-- modify the following text as appropriate --> + 組み込み向け言語CbCのGCC上の実装 <span style="font-size:70%;">http://www.cr.ie.u-ryukyu.ac.jp/~kent/slide/final.html</span><br /> + <!--Event, Location, Month Year--> + </div> +</div> + +<div class="slide top"> + <h1>組み込み向け言語Continuation based CのGCC上の実装</h1> + <p> + 与儀健人 (並列信頼研究室) + <<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>> + </p> + <!--img src="../Slidy/keys.jpg" class="cover" + alt="W3C as letters on 3 plastic buttons from a keyboard" /--> + <!--h2>ゼミ, 河野研, Sep, 2009</h2--> +</div> + +<div class="slide"> + <h1>研究の背景</h1> + <ul> + <li>ソフトウェアは今も大規模・複雑化が続いている</li> + <li>しかし、ソフトウェアのバグを発見するのは難しい</li> + <li style="marker:none;"/> + <li>組込みやReal-time処理の需要も増大してる</li> + <li>高速な応答が要求される組込み処理にはハードウェアに近い言語が適している</li> + </ul> + <p class="subtitle">なにが問題を複雑にしているのか？</p> + <ul> + <li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li> + <li>現存する記述言語は状態遷移の記述に向いていない</li> + <li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li> + </ul> +</div> + +<div class="slide" style="font-size:95%"> + <h1>研究目的</h1> + <p class="subtitle"> + 状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する + </p> + <ul> + <li>組込み、通信プロトコル、Real-time処理などの記述に向いている</li> + <li>状態遷移を直接記述するため、タブロー法での検証に有利</li> + <li>関数より細かく、ステートメントより大きい処理単位</li> + <li>細かい単位でソースコードレベルの最適化を可能にする</li> + </ul> + <p class="subtitle">条件</p> + <ul> + <li>既存のソフトウェアは膨大であり、無駄にはできない</li> + <li>互換性が必須条件</li> + <li>Cからの変換、Cへの変換ができる事が望ましい</li> + </ul> +</div> + +<div class="slide"> + <h1>Continuation based Cの提案</h1> + <p class="subtitle">継続を基本とする記述言語CbC</p> + <ul> + <li>環境を保持しない継続、<dfn>軽量継続</dfn>を導入</li> + <li>軽量継続で<em class="weak">状態遷移が明確</em>になる</li> + <li>関数の代わりとなる処理単位<dfn>コードセグメント</dfn></li> + <li>関数 > コードセグメント > ステートメント</li> + <li>for, whileなどのループも軽量継続で実現できる</li> + <li>Cとの相互利用のための構文<dfn>環境付き継続</dfn> + <ul> + <li>このCとの相互利用可能なCbCは<em>C with Continuation</em>と呼ばれる</li> + </ul> + </li> + </ul> + <p class="subtitle"></p> +</div> + +<div class="slide"> + <h1>継続とはなんなのか？</h1> + <p class="subtitle">継続</p> + <ul> + <li>現在の処理を続行するための情報 + <ul> + <li>Cならば続く命令のアドレスや</li> + <li>命令に必要な値、</li> + <li>スタックなど、その環境全てを含む</li> + </ul> + </li> + </ul> + <p class="subtitle">CbCでの軽量継続</p> + <ul> + <li>継続からスタックに関する情報を落とす</li> + <li>続く命令とデータのみのシンプルな継続</li> + <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li> + </ul> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>コードセグメントと軽量継続の記述</h1> + <pre style="float:right; width-max:45%"> +<code>typedef code (*NEXT)(int); +int main(int argc, char **argv) { + int i; + i = atoi(argv[1]); + goto factor(i, print_fact); +} +<em>code factor(int x, NEXT next)</em> { + goto factor0(1, x, next); +} +code factor0(int prod,int x,NEXT next) { + if (x >= 1) { + goto factor0(prod*x, x-1, next); + } else { + <em>goto (*next)(prod);</em> + } +} +code print_fact(int value) { + printf("factorial = %d\n", value); + exit(0); +} </code></pre> + <p class="subtitle">実際のプログラム記述は？</p> + <ul> + <li>コードセグメント定義 + <ul> + <li><code>codeキーワードで宣言</code></li> + <li>書式は関数と同じ</li> + </ul> + </li> + <li>軽量継続制御 + <ul> + <li><code>goto</code>キーワードと引数</li> + <li>コードセグメントの最初に飛ぶ</li> + <li>コードセグメントポインタによる間接継続も可能</li> + </ul> + </li> + </ul> +</div> + +<div class="slide"> + <h1>これまでのCbC</h1> + <p class="subtitle"></p> + <dl> + <dt>2000</dt> + <dd>micro-cをベースとしたコンパイラの完成<br/> + x86, PowerPC, ARM, MIPS. + </dd> + <dt>2002</dt> + <dd>CbCを用いた分散計算</dd> + <dt>2005</dt> + <dd>CbCを用いたプログラム分割手法</dd> + <dt>2006</dt> + <dd>CbCによるSPUマシンのシミュレータ</dd> + <dt>2007</dt> + <dd>時相論理をベースとしたCbCプログラムの検証</dd> + <dt>2008</dt> + <dd>GCCをベースとしたコンパイラが開発される</dd> + <dt>2010</dt> + <dd>GCCベースコンパイラを実用レベルに拡張</dd> + </dl> +</div> + +<div class="slide"> + <h1>本研究での取り組み</h1> + <p class="subtitle">取り組み</p> + <dl> + <dt>First</dt> + <dd>GCCにて実用レベルのCbCプログラムを動作可能にする + <ul> + <li>軽量継続の実装、これまでの制限の除去</li> + <li>x86アーキテクチャにて高速化を行った</li> + </ul> + </dd> + <dt>Second</dt> + <dd>C言語との相互利用を可能にした</dd> + <dt>Third</dt> + <dd>ソースコードメンテナンス性の向上</dd> + </dl> +</div> + + + +<div class="slide"> + <h1>GNU コンパイラコレクション (GCC)</h1> + <div style="width:50%;float:right;"> + <p class="subtitle">GCCでのコンパイルの流れ</p> + <ul style="padding-left:3em"> + <li>フロントエンド</li> + <li>ミドルエンド</li> + <li>バックエンド</li> + </ul> + </div> + <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" /> +</div> + +<div class="slide"> + <h1>GNU コンパイラコレクション (GCC)</h1> + <div style="width:50%;float:right;"> + <p class="subtitle">GCCでのコンパイルの流れ</p> + <ul style="padding-left:3em"> + <li>フロントエンド</li> + <li>ミドルエンド</li> + <li>バックエンド</li> + </ul> + </div> + <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" /> +</div> + + +<div class="slide"> + <h1>GCC フロントエンド</h1> + <p class="subtitle">GCCにおける構文解析部</p> + <ul class="outline"> + <li>C,Java,Adaなど、言語毎に違う</li> + <li>解析した構文は<dfn>Generic</dfn>という構文木に構築</li> + <li>さらに静的単一代入と呼ばれる手法で<dfn>GIMPLE</dfn>という構文木に変換</li> + <li>最終的にこのGIMPLE構文木をミドルエンドに渡す</li> + <li>GIMPLEの内部表現例 + <pre><code> + <call_expr 0xb7bc7850 + type <void_type 0xb7cc9270 void VOID + align 8 symtab 0 alias set -1 canonical type 0xb7cc9270 + pointer_to_this <pointer_type 0xb7cc92d8>> + side-effects addressable tree_5 + fn <var_decl 0xb7d65370 D.2156 + type <pointer_type 0xb7da74e0 type <function_type 0xb7da7478> + unsigned SI + size <integer_cst 0xb7cb36ac constant 32> + unit size <integer_cst 0xb7cb3498 constant 4> + align 32 symtab 0 alias set -1 structural equality> + used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 context <function_decl 0xb7da2c80 returner> + (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars) + (const_int -12 [0xfffffff4])) [0 D.2156+0 S4 A32]) + chain <var_decl 0xb7d653c8 D.2157 type <pointer_type 0xb7cc92d8> + used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 context <function_decl 0xb7da2c80 returner> + (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars) + (const_int -8 [0xfffffff8])) [0 D.2157+0 S4 A32]) chain <var_decl 0xb7d65420 D.2158>>> arg 0 <var_decl 0xb7d653c8 D.2157> + arg 1 <var_decl 0xb7d65420 D.2158 + type <pointer_type 0xb7da7270 stack type <void_type 0xb7cc9270 void> + sizes-gimplified unsigned SI size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8 + pointer_to_this <pointer_type 0xb7bb7000>> + used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 context <function_decl 0xb7da2c80 returner> + (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars) + (const_int -4 [0xfffffffc])) [0 D.2158+0 S4 A32])> + quicksort/quicksort_cbc.cbc:29:7> + </code></pre> + <p class="subtitle">全ての構文はこのGIMPLEで表される</p> + </li> + </ul> + <p class="subtitle incremental">つまり、主に修正すべきはこのフロントエンドとなる</p> +</div> + +<div class="slide" style="font-size:95%"> + <h1>GCC ミドルエンド</h1> + <p class="subtitle">GIMPLEからRTLへの変換と最適化</p> + <ul class="outline"> + <li><dfn>pass</dfn>と呼ばれる様々な処理の集合体</li> + <li>登録されたpassを一つ一つ実行する</li> + <li>最初にGIMPLEの最適化がたくさんある</li> + <li>そしてもっとも重要なGIMPLEから<dfn>RTL</dfn>への変換</li> + <li>最後にRTLの最適化がまた大量にある + <pre style="font-size:80%"><code> + p = &all_lowering_passes; + NEXT_PASS (pass_remove_useless_stmts); + NEXT_PASS (pass_mudflap_1); + NEXT_PASS (pass_lower_omp); + NEXT_PASS (pass_lower_cf); + NEXT_PASS (pass_refactor_eh); + NEXT_PASS (pass_lower_eh); + NEXT_PASS (pass_build_cfg); + NEXT_PASS (pass_lower_complex_O0); + NEXT_PASS (pass_lower_vector); +#ifndef noCbC + //NEXT_PASS (pass_warn_function_return); +#else + NEXT_PASS (pass_warn_function_return); +#endif + NEXT_PASS (pass_build_cgraph_edges); + NEXT_PASS (pass_inline_parameters); + *p = NULL; + + /* Interprocedural optimization passes. */ + p = &all_ipa_passes; + NEXT_PASS (pass_ipa_function_and_variable_visibility); + NEXT_PASS (pass_ipa_early_inline); + { + struct opt_pass **p = &pass_ipa_early_inline.pass.sub; + NEXT_PASS (pass_early_inline); + NEXT_PASS (pass_inline_parameters); + NEXT_PASS (pass_rebuild_cgraph_edges); + } + NEXT_PASS (pass_early_local_passes); + { + struct opt_pass **p = &pass_early_local_passes.pass.sub; + NEXT_PASS (pass_tree_profile); + NEXT_PASS (pass_cleanup_cfg); + NEXT_PASS (pass_init_datastructures); + NEXT_PASS (pass_expand_omp); + + NEXT_PASS (pass_referenced_vars); + NEXT_PASS (pass_reset_cc_flags); + NEXT_PASS (pass_build_ssa); + NEXT_PASS (pass_early_warn_uninitialized); + NEXT_PASS (pass_all_early_optimizations); + { + struct opt_pass **p = &pass_all_early_optimizations.pass.sub; + NEXT_PASS (pass_rebuild_cgraph_edges); + NEXT_PASS (pass_early_inline); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_ccp); + NEXT_PASS (pass_forwprop); + NEXT_PASS (pass_update_address_taken); + NEXT_PASS (pass_sra_early); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_merge_phi); + NEXT_PASS (pass_cd_dce); + NEXT_PASS (pass_simple_dse); + NEXT_PASS (pass_tail_recursion); + NEXT_PASS (pass_convert_switch); + NEXT_PASS (pass_profile); + } + NEXT_PASS (pass_release_ssa_names); + NEXT_PASS (pass_rebuild_cgraph_edges); + NEXT_PASS (pass_inline_parameters); + } + NEXT_PASS (pass_ipa_increase_alignment); + NEXT_PASS (pass_ipa_matrix_reorg); + NEXT_PASS (pass_ipa_cp); + NEXT_PASS (pass_ipa_inline); + NEXT_PASS (pass_ipa_reference); + NEXT_PASS (pass_ipa_pure_const); + NEXT_PASS (pass_ipa_type_escape); + NEXT_PASS (pass_ipa_pta); + NEXT_PASS (pass_ipa_struct_reorg); + *p = NULL; + + /* These passes are run after IPA passes on every function that is being + output to the assembler file. */ + p = &all_passes; + NEXT_PASS (pass_all_optimizations); + { + struct opt_pass **p = &pass_all_optimizations.pass.sub; + /* Initial scalar cleanups before alias computation. + They ensure memory accesses are not indirect wherever possible. */ + NEXT_PASS (pass_strip_predict_hints); + NEXT_PASS (pass_update_address_taken); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_complete_unrolli); + NEXT_PASS (pass_ccp); + NEXT_PASS (pass_forwprop); + /* Ideally the function call conditional + dead code elimination phase can be delayed + till later where potentially more opportunities + can be found. Due to lack of good ways to + update VDEFs associated with the shrink-wrapped + calls, it is better to do the transformation + here where memory SSA is not built yet. */ + NEXT_PASS (pass_call_cdce); + /* pass_build_alias is a dummy pass that ensures that we + execute TODO_rebuild_alias at this point. Re-building + alias information also rewrites no longer addressed + locals into SSA form if possible. */ + NEXT_PASS (pass_build_alias); + NEXT_PASS (pass_return_slot); + NEXT_PASS (pass_phiprop); + NEXT_PASS (pass_fre); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_merge_phi); + NEXT_PASS (pass_vrp); + NEXT_PASS (pass_dce); + NEXT_PASS (pass_cselim); + NEXT_PASS (pass_tree_ifcombine); + NEXT_PASS (pass_phiopt); + NEXT_PASS (pass_tail_recursion); + NEXT_PASS (pass_ch); + NEXT_PASS (pass_stdarg); + NEXT_PASS (pass_lower_complex); + NEXT_PASS (pass_sra); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_dominator); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); + NEXT_PASS (pass_dse); + NEXT_PASS (pass_reassoc); + NEXT_PASS (pass_dce); + NEXT_PASS (pass_forwprop); + NEXT_PASS (pass_phiopt); + NEXT_PASS (pass_object_sizes); + NEXT_PASS (pass_ccp); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_fold_builtins); + NEXT_PASS (pass_cse_sincos); + NEXT_PASS (pass_split_crit_edges); + NEXT_PASS (pass_pre); + NEXT_PASS (pass_sink_code); + NEXT_PASS (pass_tree_loop); + { + struct opt_pass **p = &pass_tree_loop.pass.sub; + NEXT_PASS (pass_tree_loop_init); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_dce_loop); + NEXT_PASS (pass_lim); + NEXT_PASS (pass_predcom); + NEXT_PASS (pass_tree_unswitch); + NEXT_PASS (pass_scev_cprop); + NEXT_PASS (pass_empty_loop); + NEXT_PASS (pass_record_bounds); + NEXT_PASS (pass_check_data_deps); + NEXT_PASS (pass_loop_distribution); + NEXT_PASS (pass_linear_transform); + NEXT_PASS (pass_graphite_transforms); + NEXT_PASS (pass_iv_canon); + NEXT_PASS (pass_if_conversion); + NEXT_PASS (pass_vectorize); + { + struct opt_pass **p = &pass_vectorize.pass.sub; + NEXT_PASS (pass_lower_vector_ssa); + NEXT_PASS (pass_dce_loop); + } + NEXT_PASS (pass_complete_unroll); + NEXT_PASS (pass_parallelize_loops); + NEXT_PASS (pass_loop_prefetch); + NEXT_PASS (pass_iv_optimize); + NEXT_PASS (pass_tree_loop_done); + } + NEXT_PASS (pass_cse_reciprocals); + NEXT_PASS (pass_convert_to_rsqrt); + NEXT_PASS (pass_reassoc); + NEXT_PASS (pass_vrp); + NEXT_PASS (pass_dominator); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); + NEXT_PASS (pass_cd_dce); + NEXT_PASS (pass_tracer); + + /* FIXME: If DCE is not run before checking for uninitialized uses, + we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c). + However, this also causes us to misdiagnose cases that should be + real warnings (e.g., testsuite/gcc.dg/pr18501.c). + + To fix the false positives in uninit-5.c, we would have to + account for the predicates protecting the set and the use of each + variable. Using a representation like Gated Single Assignment + may help. */ + NEXT_PASS (pass_late_warn_uninitialized); + NEXT_PASS (pass_dse); + NEXT_PASS (pass_forwprop); + NEXT_PASS (pass_phiopt); + NEXT_PASS (pass_tail_calls); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_uncprop); + } + NEXT_PASS (pass_del_ssa); + NEXT_PASS (pass_nrv); + NEXT_PASS (pass_mark_used_blocks); + NEXT_PASS (pass_cleanup_cfg_post_optimizing); + + NEXT_PASS (pass_warn_function_noreturn); + NEXT_PASS (pass_free_datastructures); + NEXT_PASS (pass_mudflap_2); + + NEXT_PASS (pass_free_cfg_annotations); + <em>NEXT_PASS (pass_expand);</em> + NEXT_PASS (pass_rest_of_compilation); + { + struct opt_pass **p = &pass_rest_of_compilation.pass.sub; + NEXT_PASS (pass_init_function); + NEXT_PASS (pass_jump); + NEXT_PASS (pass_rtl_eh); + NEXT_PASS (pass_initial_value_sets); + NEXT_PASS (pass_unshare_all_rtl); + NEXT_PASS (pass_instantiate_virtual_regs); + NEXT_PASS (pass_into_cfg_layout_mode); + NEXT_PASS (pass_jump2); + NEXT_PASS (pass_lower_subreg); + NEXT_PASS (pass_df_initialize_opt); + NEXT_PASS (pass_cse); + NEXT_PASS (pass_rtl_fwprop); + NEXT_PASS (pass_gcse); + NEXT_PASS (pass_rtl_ifcvt); + /* Perform loop optimizations. It might be better to do them a bit + sooner, but we want the profile feedback to work more + efficiently. */ + NEXT_PASS (pass_loop2); + { + struct opt_pass **p = &pass_loop2.pass.sub; + NEXT_PASS (pass_rtl_loop_init); + NEXT_PASS (pass_rtl_move_loop_invariants); + NEXT_PASS (pass_rtl_unswitch); + NEXT_PASS (pass_rtl_unroll_and_peel_loops); + NEXT_PASS (pass_rtl_doloop); + NEXT_PASS (pass_rtl_loop_done); + *p = NULL; + } + NEXT_PASS (pass_web); + NEXT_PASS (pass_jump_bypass); + NEXT_PASS (pass_cse2); + NEXT_PASS (pass_rtl_dse1); + NEXT_PASS (pass_rtl_fwprop_addr); + NEXT_PASS (pass_reginfo_init); + NEXT_PASS (pass_inc_dec); + NEXT_PASS (pass_initialize_regs); + NEXT_PASS (pass_outof_cfg_layout_mode); + NEXT_PASS (pass_ud_rtl_dce); + NEXT_PASS (pass_combine); + NEXT_PASS (pass_if_after_combine); + NEXT_PASS (pass_partition_blocks); + NEXT_PASS (pass_regmove); + NEXT_PASS (pass_split_all_insns); + NEXT_PASS (pass_lower_subreg2); + NEXT_PASS (pass_df_initialize_no_opt); + NEXT_PASS (pass_stack_ptr_mod); + NEXT_PASS (pass_mode_switching); + NEXT_PASS (pass_see); + NEXT_PASS (pass_match_asm_constraints); + NEXT_PASS (pass_sms); + NEXT_PASS (pass_sched); + NEXT_PASS (pass_subregs_of_mode_init); + NEXT_PASS (pass_ira); + NEXT_PASS (pass_subregs_of_mode_finish); + NEXT_PASS (pass_postreload); + { + struct opt_pass **p = &pass_postreload.pass.sub; + NEXT_PASS (pass_postreload_cse); + NEXT_PASS (pass_gcse2); + NEXT_PASS (pass_split_after_reload); + NEXT_PASS (pass_branch_target_load_optimize1); + NEXT_PASS (pass_thread_prologue_and_epilogue); + NEXT_PASS (pass_rtl_dse2); + NEXT_PASS (pass_rtl_seqabstr); + NEXT_PASS (pass_stack_adjustments); + NEXT_PASS (pass_peephole2); + NEXT_PASS (pass_if_after_reload); + NEXT_PASS (pass_regrename); + NEXT_PASS (pass_cprop_hardreg); + NEXT_PASS (pass_fast_rtl_dce); + NEXT_PASS (pass_reorder_blocks); + NEXT_PASS (pass_branch_target_load_optimize2); + NEXT_PASS (pass_leaf_regs); + NEXT_PASS (pass_split_before_sched2); + NEXT_PASS (pass_sched2); + NEXT_PASS (pass_stack_regs); + { + struct opt_pass **p = &pass_stack_regs.pass.sub; + NEXT_PASS (pass_split_before_regstack); + NEXT_PASS (pass_stack_regs_run); + } + NEXT_PASS (pass_compute_alignments); + NEXT_PASS (pass_duplicate_computed_gotos); + NEXT_PASS (pass_variable_tracking); + NEXT_PASS (pass_free_cfg); + NEXT_PASS (pass_machine_reorg); + NEXT_PASS (pass_cleanup_barriers); + NEXT_PASS (pass_delay_slots); + NEXT_PASS (pass_split_for_shorten_branches); + NEXT_PASS (pass_convert_to_eh_region_ranges); + NEXT_PASS (pass_shorten_branches); + NEXT_PASS (pass_set_nothrow_function_flags); + NEXT_PASS (pass_final); + } + NEXT_PASS (pass_df_finish); + } + NEXT_PASS (pass_clean_state); + *p = NULL; + </code></pre> + </li> + </ul> + <p class="subtitle">RTL</p> + <ul class="outline"> + <li>一般的には中間コードとも呼ばれる</li> + <li>アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現</li> + <li>RTLの例 +<pre><code>(insn 27 26 0 quicksort/quicksort_cbc.cbc:29 (parallel [ + (set (reg/f:SI 7 sp) + (plus:SI (reg/f:SI 7 sp) + (const_int -1024 [0xfffffc00]))) + (clobber (reg:CC 17 flags)) + ]) -1 (nil)) +</code></pre> + </li> + </ul> +</div> + +<div class="slide"> + <h1>バックエンド</h1> + <p class="subtitle">RTLからアセンブラに変換する処理</p> + <ul class="outline"> + <li><dfn>Machine Description(md)</dfn>と呼ばれる変換規則を用いる</li> + <li>アーキテクチャ毎にこのmdが必要になる</li> + <li>新しいアーキテクチャの対応はこのバックエンドを修正することになる</li> + <li>mdの例 + <pre><code> +(define_insn "cmpdi_ccno_1_rex64" + [(set (reg FLAGS_REG) + (compare (match_operand:DI 0 "nonimmediate_operand" "r,?mr") + (match_operand:DI 1 "const0_operand" "")))] + "TARGET_64BIT && ix86_match_ccmode (insn, CCNOmode)" + "@ + test{q}\t%0, %0 + cmp{q}\t{%1, %0|%0, %1}" + [(set_attr "type" "test,icmp") + (set_attr "length_immediate" "0,1") + (set_attr "mode" "DI")]) + +(define_insn "*cmpdi_minus_1_rex64" + [(set (reg FLAGS_REG) + (compare (minus:DI (match_operand:DI 0 "nonimmediate_operand" "rm,r") + (match_operand:DI 1 "x86_64_general_operand" "re,mr")) + (const_int 0)))] + "TARGET_64BIT && ix86_match_ccmode (insn, CCGOCmode)" + "cmp{q}\t{%1, %0|%0, %1}" + [(set_attr "type" "icmp") + (set_attr "mode" "DI")]) + </code></pre></li> + </ul> +</div> + +<div class="slide"> + <h1>本研究での取り組み</h1> + <p class="subtitle">取り組み</p> + <dl> + <dt>First</dt> + <dd>GCCにて実用レベルのCbCプログラムを動作可能にする + <ul> + <li>軽量継続の実装、これまでの制限の除去</li> + <li>x86アーキテクチャにて高速化を行った</li> + </ul> + </dd> + <dt>Second</dt> + <dd>C言語との互換性の向上</dd> + <dt>Third</dt> + <dd>ソースコードメンテナンス性の向上</dd> + </dl> +</div> + + + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">軽量継続を実装するには？</p> + <ul> + <li>micro-cは元より軽量継続を考慮して良く設計されている</li> + <li>GCCでは<em class="weak">あくまで関数</em>がベース</li> + <li>micro-Cと同じ命令列を出力させるのは難しい</li> + <li>関数コール(call命令)ではもちろんダメ</li> + <li>必ず<em>jmp命令</em>を出力しないといけない</li> + <li>スタックを拡張するのもダメ</li> + </ul> + <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p> +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出ってなに？</p> + <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" /> + <ul> + <li>リターンの直前の関数呼び出しのこと</li> + <li>GCCが最適化してくれる (<em>TCE</em>)</li> + <li>元の関数に戻らないため少し高速に</li> + <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li> + </ul> +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出ってなに？</p> + <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" /> + <ul> + <li>リターンの直前の関数呼び出しのこと</li> + <li>GCCが最適化してくれる (<em>TCE</em>)</li> + <li>元の関数に戻らないため少し高速に</li> + <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li> + </ul> + <p class="subtitle incremental">軽量継続ではこの末尾呼出(TCE)を強制する！</p> +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出による軽量継続の実装</p> + <ul> + <li>全ての軽量継続は末尾呼出と解釈する</li> + <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li> + <li><code>goto cs(20, 30);</code></li> + <li><code>cs(20, 30); return;</code></li> + </ul> + <p class="subtitle">ある条件で末尾呼出が行われなくなる</p> + <ol> + <li>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</li> + <li>引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合</li> + </ol> +</div> +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出による軽量継続の実装</p> + <ul> + <li>全ての軽量継続は末尾呼出と解釈する</li> + <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li> + <li><code>goto cs(20, 30);</code></li> + <li><code>cs(20, 30); return;</code></li> + </ul> + <p class="subtitle">ある条件で末尾呼出が行われなくなる</p> + <ol> + <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li> + <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li> + </ol> +</div> + + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">引数順序の問題の解決</p> + <ul> + <li>問題となる例 +<pre><code>code somesegment(int a, int b, int c) { + /∗ do something ∗/ + goto nextsegment(b, c, a); +} +</code></pre> + </li> + <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li> + <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li> + <li>必ず一つ(1ワード)以上の一時変数が必要になる</li> + </ul> + +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">全ての引数を一時変数に退避</p> + <ul> + <li>次の様に構文木を変更する +<pre><code>code somesegment(int a, int b, int c) { + int a1, b1, c1; + /∗ do something ∗/ + a1=a; b1=b; c1=c; + goto nextsegment(b1, c1, a1); +} +</code></pre> + </li> + <li>これにより、引数順序を考える必要はなくなる</li> + <li>代わりに、メモリアクセスが大量に発生</li> + <li>しかし、これはGCCの最適化で除去される</li> + </ul> + + <p class="subtitle">これで軽量継続が実装された</p> +</div> + + +<div class="slide"> + <h1>First: x86における高速化</h1> + <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p> + <ul> + <li>特にx86アーキテクチャ</li> + <li><em class="weak">あくまで関数がベース</em>なので</li> + <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li> + <li>これをレジスタにすれば高速化が可能</li> + </ul> + <p class="subtitle">fastcallの導入</p> + <ul> + <li>GCCの独自拡張機能</li> + <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li> + </ul> +</div> + +<div class="slide"> + <h1>First: x86における高速化</h1> + <p class="subtitle">fastcallの強制</p> + <ul> + <li>通常は以下の様に定義される +<pre><code>__code current(int a, int b, int c) __attribute__((fastcall)); +</code></pre></li> + <li>しかしこれを毎回ユーザが書くのは変</li> + <li>やはりフロントエンドにて、強制するべき</li> + <li>型の構文木を生成した際にfastcall属性を付加</li> + </ul> + <p class="subtitle">実際の出力はどうなる？</p> + <div style="width:70%;margin:1em auto 0;"> +<pre><code>__code current(int a, int b, int c) { + goto next(10, 20, 30); +} +</code></pre> + </div> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>First: x86における高速化</h1> + <p class="subtitle">実際の出力アセンブラ</p> + <div style="width:50%;float:left;margin-left:auto;"> + <p style="margin:0;text-align:center">fastcallにした場合</p> +<pre><code>current: + subl $12, %esp + movl $30, 16(%esp) + movl $20, %edx + movl $10, %ecx + addl $12, %esp + jmp next +</code></pre> + </div> + <div style="width:50%;float:right;margin-right:auto;"> + <p style="margin:0;text-align:center">normalcallの場合</p> +<pre><code>current: + pushl %ebp + movl %esp, %ebp + movl $30, 16(%ebp) + movl $20, 12(%ebp) + movl $10, 8(%ebp) + leave + jmp next +</code></pre> + </div> + <br clear="all" /> + <ul> + <li>命令数ではほとんど変化はない</li> + <li>引数2つがレジスタecxとedxに格納されるようになった</li> + <li>そのためメモリアクセスが減る</li> + <li>これで高速化されるはず</li> + </ul> +</div> + + +<div class="slide"> + <h1>First: CbCコンパイラ実装の評価</h1> + <p class="subtitle">CbCGCCとmicro-cで性能の比較</p> + <ul> + <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li> + <li>コンパイラの出力した実行ファイルを比較</li> + <li>CbCでのquicksort例題を用意</li> + <li>実行速度、ファイルサイズ</li> + <li>比較対象はまずは旧CbCGCC、それとmicro-c</li> + </ul> + <p class="subtitle">実行環境</p> + <ul> + <li>CbCGCC、micro-cでともに実行可能な環境を選択</li> + <li>アーキテクチャは x86, PowerPC(Cell含む)</li> + <li>OSはLinuxとOS Xを使用する</li> + </ul> +</div> + +<div class="slide"> + <h1>First: 性能評価（速度比較） vs.旧ver</h1> + <p class="subtitle">速度測定結果(単位:秒)</p> + <table> + <tr> + <th></th> + <th colspan="2">新CbCGCC</th> + <th colspan="2">旧CbCGCC</th> + </tr> + <tr> + <td></td> + <th>最適化無し</th> + <th>最適化有り</th> + <th>最適化無し</th> + <th>最適化有り</th> + </tr> + <tr> + <td>x86/OS X</td> + <td>5.907</td> + <td>2.434</td> + <td>4.668</td> + <td>3.048</td> + </tr> + <tr> + <td>x86/Linux</td> + <td>5.715</td> + <td>2.401</td> + <td>4.525</td> + <td>2.851</td> + </tr> + </table> + <p class="subtitle">評価</p> + <ul> + <li>最適化無の場合は遅くなった </li> + <li>一時変数への確保があるのでこれは予想通り</li> + <li>最適化を行うと、<em>約20%の高速化に成功</em></li> + <li>fastcallの効果が十分に出ている</li> + </ul> +</div> + + +<div class="slide"> + <h1>First: 性能評価（速度比較）</h1> + <p class="subtitle">速度測定結果(単位:秒)</p> + <table> + <tr> + <td></td> + <td>最適化なしのGCC</td> + <td>最適化付きのGCC</td> + <td>micro-c</td> + </tr> + <tr> + <td>x86/OS X</td> + <td>5.901</td> + <td>2.434</td> + <td>2.857</td> + </tr> + <tr> + <td>x86/Linux</td> + <td>5.732</td> + <td>2.401</td> + <td>2.254</td> + </tr> + <tr> + <td>ppc/OS X</td> + <td>14.875</td> + <td>2.146</td> + <td>4.811</td> + </tr> + <tr> + <td>ppc/Linux</td> + <td>19.793</td> + <td>3.955</td> + <td>6.454</td> + </tr> + <tr> + <td>ppc/PS3</td> + <td>39.176</td> + <td>5.874</td> + <td>11.121</td> + </tr> + </table> + <p class="subtitle">結果(micro-cとの比較)</p> + <ul> + <li>x86では速度にあまり差が出なかった</li> + <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li> + <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li> + </ul> +</div> + +<div class="slide"> + <h1>First: 性能評価（速度比較）</h1> + <p class="subtitle">結果(micro-cとの比較)</p> + <ul> + <li>x86では速度にあまり差が出なかった</li> + <li>PowerPCではCbCGCCが2倍ほど早い</li> + </ul> + <p class="subtitle">この違いはどこから？</p> + <ul style="font-size:95%;"> + <li>実際にアセンブラを出力して比較、その結果</li> + <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li> + <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li> + <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li> + <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li> + </ul> +</div> + +<div class="slide"> + <h1>First: 性能評価（サイズ比較）</h1> + <p class="subtitle">ファイルサイズの比較</p> + <ul> + <li>組み込み系ではメモリ使用量が肝心</li> + <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li> + <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li> + </ul> + <p class="subtitle">結果</p> + <table> + <tr> + <td></td> + <th>CbCGCC<br/>速度最適化</th> + <th>CbCGCC<br/>サイズ最適化</th> + <th>micro-c</th> + </tr> + <tr> + <td>x86/OS X</td> + <td>9176</td> + <td>9176</td> + <td>9172</td> + </tr> + <tr> + <td>x86/Linux</td> + <td>5752</td> + <td>5752</td> + <td>5796</td> + </tr> + <tr> + <td>ppc/OS X</td> + <td>8576</td> + <td>8576</td> + <td>12664</td> + </tr> + <tr> + <td>ppc/Linux</td> + <td>10068</td> + <td>10068</td> + <td>9876</td> + </tr> + <tr> + <td>ppc/PS3</td> + <td>6960</td> + <td>6728</td> + <td>8636</td> + </tr> + </table> + <p class="subtitle">結果考察</p> + <ul> + <li>x86ではファイルサイズの差がない</li> + <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li> + <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li> + </ul> +</div> + + +<div class="slide"> + <h1>Second: Cとの相互利用</h1> + <p class="subtitle">なぜそれが必要か</p> + <ul> + <li>C <=> CbC の変換が可能なので互換性はある</li> + <li>しかし、ソースコード上での互換性もある事が望ましい</li> + <li>CbCからCの関数を呼び出すのは問題ない</li> + <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li> + </ul> + <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p> + <ul> + <li>軽量継続に、スタックの情報を加える</li> + <li>つまり通常の「継続」と同じ</li> + <li>関数からのみ使用可能</li> + </ul> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>Second: Cとの相互利用</h1> + <pre style="float:right; width-max:45%"> +<code>typedef code (*NEXT)(int); +int main(int argc, char **argv) { + int i,a; + i = atoi(argv[1]); + <em>a = factor(i);</em> + printf("%d! = %d\n", a); +} +int factor(int x) { + NEXT ret = <em>__return</em>; + goto factor0(1, x, ret); +} +code +factor0(int prod,int x,NEXT next) { + if (x >= 1) { + goto factor0(prod*x, x-1, next); + } else { + <em>goto (*next)(prod);</em> + } +} +</code></pre> + <p class="subtitle">環境付き継続の使用例</p> + <ul> + <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li> + <li>コードセグメントからは通常のコードセグメントポインタに見える</li> + <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li> + </ul> +</div> + +<div class="slide"> + <h1>Second: Cとの相互利用</h1> + <p class="subtitle">どのように実装する？</p> + <ol> + <li>setjmp()/longjmp()を使って実装可能 + <ul> + <li>Cの標準ライブラリの関数</li> + <li>しかし余計な環境も保持するためオーバヘッドが大きい</li> + <li>継続の際に渡す引数が一つ増えてしまう</li> + </ul></li> + <li>内部関数 + <ul> + <li>GCCの独自拡張</li> + <li>関数内に関数を定義可能</li> + <li><em>内部関数から外の関数のラベルにgotoできる</em></li> + </ul></li> + </ol> + <p class="subtitle">内部関数が使いやすい</p> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>Second: Cとの相互利用</h1> + <p class="subtitle">具体的には</p> + <ul> + <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li> + <li>内部関数の中からは外の関数にgotoして脱出</li> + </ul> + <pre><code>int factor(int x) { + int retval; + + <em class="weak">code __return(int val) { + retval = val; + goto label; + } + if (0) { + label: + return retval; + }</em> + + NEXT ret = <em>__return</em>; + goto factor0(1, x, ret); +} </code></pre> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>Second: Cとの相互利用・評価</h1> + <p class="subtitle">この取り組みにより</p> + <ul> + <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li> + <li>ソースコードレベルで、Cと相互に利用することが可能になった</li> + </ul> +</div> + +<div class="slide"> + <h1>Third: メンテナンス性の向上</h1> + <p class="subtitle">GCCのアップデートリリースは早い</p> + <ul> + <li>リリースだけで年に5回のペース</li> + <li>その度にバグの修正やコードの改善が入る</li> + <li>問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること</li> + </ul> + <p class="subtitle">このリリースに追従して差分をアップデートしたい</p> + <ul> + <li>GCC本家にマージしてもらうのが一番良いが難しい</li> + <li></li> + </ul> +</div> + +<div class="slide"> + <h1>Third: メンテナンス性の向上</h1> + <img style="width:60%;float:right;" src="figures/gcc-repository.png" /> + <p class="subtitle">二つのリポジトリ管理</p> + <ul> + <li>本家のリリースをそのままコミットするリポジトリ GCC_copy</li> + <li>CbCの修正が加えられたリポジトリ CbCGCC</li> + <li>Mercurialによる分散リポジトリ管理</li> + <li>CbCGCC は GCC_copyをクローン（ブランチ）して作成する</li> + </ul> + <p class="subtitle"></p> +</div> + + +<div class="slide"> + <h1>Third: メンテナンス性の向上</h1> + <p class="subtitle">アップデート手順</p> + <ul> + <li>GCC-copyリポジトリにて + <ol> + <li>GCC-copyリポジトリのファイルをすべて消す</li> + <li>GCCの最新バージョンをリポジトリ内に展開</li> + <li>追加ファイル、削除ファイルを確認</li> + <li>コミット、タグ付け</li> + </ol> </li> + <li>CbCGCCリポジトリにて + <ol> + <li>GCC-copyからpull.</li> + <li>hg mergeでマージ実行</li> + <li>衝突があればソースコードをを修正</li> + <li>ビルドテスト</li> + <li>コミット、タグ付け</li> + </ol></li> + </ul> +</div> + +<div class="slide"> + <h1>Third: メンテナンス性の向上・比較</h1> + <p class="subtitle">これまでのアップデートは</p> + <ul> + <li>GCCの新旧の差分、CbCの差分</li> + <li>複雑なdiffをとる必要がある</li> + </ul> + <p class="subtitle">新しい管理方法により</p> + <ul> + <li>「3.衝突があればソースコードを修正」以外は機械的に実行可能</li> + <li>内部の設計が変わったなど、<em>重要な変更点にだけ集中</em>できる</li> + <li>分散管理にしたことで、移行用バージョンを分けることが可能になる</li> + </ul> +</div> + +<div class="slide"> + <h1>まとめ</h1> + <p class="subtitle">本研究での取り組み</p> + <dl> + <dt>First</dt> + <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった + <ul> + <li>軽量継続における引数順序の制限を取り除いた</li> + <li>PowerPCでの間接継続の制限を取り除いた</li> + <li>x86アーキテクチャにて高速化を行った</li> + </ul> + </dd> + <dt>Second</dt> + <dd>Cとの相互利用性の向上</dd> + <dt>Third</dt> + <dd>ソースコードメンテナンス性の向上</dd> + </dl> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>まとめ</h1> + <p class="subtitle">本研究での成果</p> + <dl> + <dt>成果1</dt> + <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった + <dt>成果2</dt> + <dd>CbCが多数のアーキテクチャに対応 + <ul> + <li>20以上のアーキテクチャ</li> + <li>特に64bitのx86, SPUがうれしい</li> + </ul> </dd> + <dt>成果3</dt> + <dd>CbCの高速化 + <ul> + <li>x86においてもmicro-cと互角の速度を達成</li> + <li>PowerPCでは2倍の速度</li> + </ul></dd> + <dt>成果4</dt> + <dd>メンテナンス性が向上</dd> + </dl> +</div> + +<div class="slide"> + <h1>今後の課題</h1> + <p class="subtitle"></p> + <ul> + <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li> + <li>タブロー方を用いた検証</li> + <li>TaskManagerのCbC実装</li> + </ul> + <p class="subtitle">CbC言語の今後</p> + <ul> + <li>オブジェクティブなCbCの設計</li> + <li>データセグメントの導入</li> + <li>スケジューラのためのリフレクション</li> + </ul> +</div> + + +<div class="slide"> + <h1>おわり</h1> + <p class="subtitle">ありがとうございました</p> +</div> + + + + + + + + + + + + + + + + + + + + +<div class="slide"> + <h1>Continuation based C</h1> + <ul> + <li>言語仕様</li> + <li>return-callから軽量継続へ</li> + <li>コードセグメント</li> + <li>状態遷移に適した言語</li> + <li>Cとの互換性</li> + </ul> +</div> + + +<div class="slide"> + <h1></h1> + <p class="subtitle"></p> + <ul> + <li></li> + <li></li> + </ul> +</div> +<div class="slide"> + <h1></h1> + <p class="subtitle"></p> + <ul> + <li></li> + <li></li> + </ul> +</div> + +<div class="slide"> + <h1></h1> + <p class="subtitle"></p> + <ul> + <li></li> + <li></li> + </ul> +</div> + + +<div class="slide"> + <h1>First: PowerPCでの間接継続</h1> + <p class="subtitle"></p> + <ul> + <li></li> + </ul> + <p class="subtitle"></p> + <div style="width:70%;margin:1em auto 0;"> +<pre><code> +</code></pre> + </div> +</div> + +<div class="slide"> + <h1>継続制御での並列代入</h1> + <p class="subtitle" style="margin:0 1em 0.1em;"> + 本当に最適化で余分なコードが消えるのか？ + </p> + <div style="width:45%;float:left;margin-left:1em;"> + 最適化しない場合 +<pre style="margin-top:0"><code> _test: + stwu r1,-64(r1) + mr r30,r1 + stw r3,88(r30) + stw r4,92(r30) + stw r5,96(r30) + lwz r0,92(r30) + stw r0,32(r30) + lwz r0,96(r30) + addic r0,r0,1 + stw r0,28(r30) + lwz r0,88(r30) + stw r0,24(r30) + lwz r3,32(r30) + lwz r4,28(r30) + lwz r5,24(r30) + addi r1,r30,64 + lwz r30,-8(r1) + lwz r31,-4(r1) + b L_next$stub +</code></pre> + </div> + <div style="width:45%;float:right;margin-right:1em;"> + 最適化した場合 +<pre><code> +_test: + mr r0,r3 + mr r3,r4 + mr r4,r5 + mr r5,r0 + b L_next$stub +</code></pre> + </div> + <div style="width:50%;float:right"> + <ul> + <li>r3:=a, r4:=b, r5:=c</li> + <li>最適化しないとload, storeが満載</li> + <li>最適化すると無駄なload, store命令が消えている</li> + <li>実際はr0を使って4命令で入れ替えられる!</li> + </ul> + </div> +</div> + +<div class="slide"> + <h1>Cとの比較について</h1> + <p class="subtitle">quicksort例題をCと比較すると</p> + <ul> + <li>現在のところ、遅くなる</li> + <li>問題はquicksortという例題では必ずスタックが必要だということ</li> + <li>例題ではスタックを自前の構造体で用意している</li> + <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li> + <li>状態遷移ベースの例題を作りたい</li> + </ul> +</div> + + +<div class="slide"> + <h1>TODO</h1> + <p class="subtitle"></p> + <ul> + <li>並列代入</li> + <li>PowerPC間接継続</li> + <li>評価結果・表</li> + <li>バックエンド</li> + <li></li> + </ul> +</div> + + +</body> +</html> +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/probation-slide/slidy.css Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,317 @@ +/* slidy.css + + Copyright (c) 2005 W3C (MIT, ERCIM, Keio), All Rights Reserved. + W3C liability, trademark, document use and software licensing + rules apply, see: + + http://www.w3.org/Consortium/Legal/copyright-documents + http://www.w3.org/Consortium/Legal/copyright-software +*/ +body +{ + margin: 0 0 0 0; + padding: 0 0 0 0; + width: 100%; + height: 100%; + color: black; + background-color: white; + font-family: "Gill Sans MT", "Gill Sans", GillSans, sans-serif; + font-size: 14pt; +} + +.hidden { display: none; visibility: hidden } + +div.toolbar { + position: fixed; z-index: 200; + top: auto; bottom: 0; left: 0; right: 0; + height: 1.2em; text-align: right; + padding-left: 1em; + padding-right: 1em; + font-size: 60%; + color: red; background: rgb(240,240,240); +} + +div.background { + display: none; +} + +div.handout { + margin-left: 20px; + margin-right: 20px; +} + +div.slide.titlepage { + text-align: center; +} + +div.slide.titlepage.h1 { + padding-top: 40%; +} + +div.slide { + z-index: 20; + margin: 0 0 0 0; + padding-top: 0; + padding-bottom: 0; + padding-left: 20px; + padding-right: 20px; + border-width: 0; + top: 0; + bottom: 0; + left: 0; + right: 0; + line-height: 120%; + background-color: transparent; +} + +/* this rule is hidden from IE 6 and below which don't support + selector */ +div.slide + div[class].slide { page-break-before: always;} + +div.slide h1 { + padding-left: 0; + padding-right: 20pt; + padding-top: 4pt; + padding-bottom: 4pt; + margin-top: 0; + margin-left: 0; + margin-right: 60pt; + margin-bottom: 0.5em; + display: block; + font-size: 160%; + line-height: 1.2em; + background: transparent; +} + +div.toc { + position: absolute; + top: auto; + bottom: 4em; + left: 4em; + right: auto; + width: 60%; + max-width: 30em; + height: 30em; + border: solid thin black; + padding: 1em; + background: rgb(240,240,240); + color: black; + z-index: 300; + overflow: auto; + display: block; + visibility: visible; +} + +div.toc-heading { + width: 100%; + border-bottom: solid 1px rgb(180,180,180); + margin-bottom: 1em; + text-align: center; +} + +pre { + font-size: 80%; + font-weight: bold; + line-height: 120%; + padding-top: 0.2em; + padding-bottom: 0.2em; + padding-left: 1em; + padding-right: 1em; + border-style: solid; + border-left-width: 1em; + border-top-width: thin; + border-right-width: thin; + border-bottom-width: thin; + border-color: #95ABD0; + color: #00428C; + background-color: #E4E5E7; +} + +li pre { margin-left: 0; } + +@media print { + div.slide { + display: block; + visibility: visible; + position: relative; + border-top-style: solid; + border-top-width: thin; + border-top-color: black; + } + div.slide pre { font-size: 60%; padding-left: 0.5em; } + div.handout { display: block; visibility: visible; } +} + +blockquote { font-style: italic } + +img { background-color: transparent } + +p.copyright { font-size: smaller } + +.center { text-align: center } +.footnote { font-size: smaller; margin-left: 2em; } + +a img { border-width: 0; border-style: none } + +a:visited { color: navy } +a:link { color: navy } +a:hover { color: red; text-decoration: underline } +a:active { color: red; text-decoration: underline } + +a {text-decoration: none} +.navbar a:link {color: white} +.navbar a:visited {color: yellow} +.navbar a:active {color: red} +.navbar a:hover {color: red} + +ul { list-style-type: square; } +ul ul { list-style-type: disc; } +ul ul ul { list-style-type: circle; } +ul ul ul ul { list-style-type: disc; } +li { margin-left: 0.5em; margin-top: 0.5em; } +li li { font-size: 85%; font-style: italic } +li li li { font-size: 85%; font-style: normal } + +div dt +{ + margin-left: 0; + margin-top: 1em; + margin-bottom: 0.5em; + font-weight: bold; +} +div dd +{ + margin-left: 2em; + margin-bottom: 0.5em; +} + + +p,pre,ul,ol,blockquote,h2,h3,h4,h5,h6,dl,table { + margin-left: 1em; + margin-right: 1em; +} + +p.subhead { font-weight: bold; margin-top: 2em; } + +.smaller { font-size: smaller } +.bigger { font-size: 130% } + +td,th { padding: 0.2em } + +ul { + margin: 0.5em 1.5em 0.5em 1.5em; + padding: 0; +} + +ol { + margin: 0.5em 1.5em 0.5em 1.5em; + padding: 0; +} + +ul { list-style-type: square; } +ul ul { list-style-type: disc; } +ul ul ul { list-style-type: circle; } +ul ul ul ul { list-style-type: disc; } + +ul li { + list-style: square; + margin: 0.1em 0em 0.6em 0; + padding: 0 0 0 0; + line-height: 140%; +} + +ol li { + margin: 0.1em 0em 0.6em 1.5em; + padding: 0 0 0 0px; + line-height: 140%; + list-style-type: decimal; +} + +li ul li { + font-size: 85%; + font-style: italic; + list-style-type: disc; + background: transparent; + padding: 0 0 0 0; +} +li li ul li { + font-size: 85%; + font-style: normal; + list-style-type: circle; + background: transparent; + padding: 0 0 0 0; +} +li li li ul li { + list-style-type: disc; + background: transparent; + padding: 0 0 0 0; +} + +li ol li { + list-style-type: decimal; +} + + +li li ol li { + list-style-type: decimal; +} + +/* + setting class="outline on ol or ul makes it behave as an + ouline list where blocklevel content in li elements is + hidden by default and can be expanded or collapsed with + mouse click. Set class="expand" on li to override default +*/ + +ol.outline li:hover { cursor: pointer } +ol.outline li.nofold:hover { cursor: default } + +ul.outline li:hover { cursor: pointer } +ul.outline li.nofold:hover { cursor: default } + +ol.outline { list-style:decimal; } +ol.outline ol { list-style-type:lower-alpha } + +ol.outline li.nofold { + padding: 0 0 0 20px; + background: transparent url(nofold-dim.gif) no-repeat 0px 0.5em; +} +ol.outline li.unfolded { + padding: 0 0 0 20px; + background: transparent url(fold-dim.gif) no-repeat 0px 0.5em; +} +ol.outline li.folded { + padding: 0 0 0 20px; + background: transparent url(unfold-dim.gif) no-repeat 0px 0.5em; +} +ol.outline li.unfolded:hover { + padding: 0 0 0 20px; + background: transparent url(fold.gif) no-repeat 0px 0.5em; +} +ol.outline li.folded:hover { + padding: 0 0 0 20px; + background: transparent url(unfold.gif) no-repeat 0px 0.5em; +} + +ul.outline li.nofold { + padding: 0 0 0 20px; + background: transparent url(nofold-dim.gif) no-repeat 0px 0.5em; +} +ul.outline li.unfolded { + padding: 0 0 0 20px; + background: transparent url(fold-dim.gif) no-repeat 0px 0.5em; +} +ul.outline li.folded { + padding: 0 0 0 20px; + background: transparent url(unfold-dim.gif) no-repeat 0px 0.5em; +} +ul.outline li.unfolded:hover { + padding: 0 0 0 20px; + background: transparent url(fold.gif) no-repeat 0px 0.5em; +} +ul.outline li.folded:hover { + padding: 0 0 0 20px; + background: transparent url(unfold.gif) no-repeat 0px 0.5em; +} + +/* for slides with class "title" in table of contents */ +a.titleslide { font-weight: bold; font-style: italic }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/probation-slide/slidy.js Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,2949 @@ +/* slidy.js + + Copyright (c) 2005-2009 W3C (MIT, ERCIM, Keio), All Rights Reserved. + W3C liability, trademark, document use and software licensing + rules apply, see: + + http://www.w3.org/Consortium/Legal/copyright-documents + http://www.w3.org/Consortium/Legal/copyright-software +*/ + +var ns_pos = (typeof window.pageYOffset!='undefined'); +var khtml = ((navigator.userAgent).indexOf("KHTML") >= 0 ? true : false); +var opera = ((navigator.userAgent).indexOf("Opera") >= 0 ? true : false); +var ie = (typeof document.all != "undefined" && !opera); +var ie7 = (!ns_pos && navigator.userAgent.indexOf("MSIE 7") != -1); +var ie8 = (!ns_pos && navigator.userAgent.indexOf("MSIE 8") != -1); +var slidy_started = false; + +// added by kent. +var showspeak = false; + +if (ie && !ie8) + document.write("<iframe id='historyFrame' src='javascript:\"<html"+"></"+"html>\"' height='1' width='1' style='position:absolute;left:-800px'></iframe>"); + +// IE only event handlers to ensure all slides are printed +// I don't yet know how to emulate these for other browsers +if (typeof beforePrint != 'undefined') +{ + window.onbeforeprint = beforePrint; + window.onafterprint = afterPrint; +} + +// to avoid a clash with other scripts or onload attribute on <body> +// we use something smarter than window.onload +//window.onload = startup; + + +if (ie) + setTimeout(ieSlidyInit, 100); +else if (document.addEventListener) + document.addEventListener("DOMContentLoaded", startup, false); + +function ieSlidyInit() +{ + if (//document.readyState == "interactive" || + document.readyState == "complete" || + document.readyState == "loaded") + { + startup(); + } + else + { + setTimeout(ieSlidyInit, 100); + } +} + +setTimeout(hideSlides, 50); + +function hideSlides() +{ + if (document.body) + document.body.style.visibility = "hidden"; + else + setTimeout(hideSlides, 50); +} + +var slidenum = 0; // integer slide count: 0, 1, 2, ... +var slides; // set to array of slide div's +var slideNumElement; // element containing slide number +var notes; // set to array of handout div's +var backgrounds; // set to array of background div's +var toolbar; // element containing toolbar +var title; // document title +var lastShown = null; // last incrementally shown item +var eos = null; // span element for end of slide indicator +var toc = null; // table of contents +var outline = null; // outline element with the focus +var selectedTextLen; // length of drag selection on document + +var viewAll = 0; // 1 to view all slides + handouts +var wantToolbar = 1; // 0 if toolbar isn't wanted +var mouseClickEnabled = true; // enables left click for next slide +var scrollhack = 0; // IE work around for position: fixed + +var helpAnchor; // used for keyboard focus hack in showToolbar() +var helpPage = "http://www.w3.org/Talks/Tools/Slidy/help.html"; +var helpText = "Navigate with mouse click, space bar, Cursor Left/Right, " + + "or Pg Up and Pg Dn. Use S and B to change font size."; + +var sizeIndex = 0; +var sizeAdjustment = 0; +var sizes = new Array("10pt", "12pt", "14pt", "16pt", "18pt", "20pt", + "22pt", "24pt", "26pt", "28pt", "30pt", "32pt"); +var okayForIncremental = incrementalElementList(); + +// needed for efficient resizing +var lastWidth = 0; +var lastHeight = 0; + +// Needed for cross browser support for relative width/height on +// object elements. The work around is to save width/height attributes +// and then to recompute absolute width/height dimensions on resizing +var objects; + +// updated to language specified by html file +var lang = "en"; + +//var localize = {}; + +// for each language there is an associative array +var strings_es = { + "slide":"pág.", + "help?":"Ayuda", + "contents?":"Índice", + "table of contents":"tabla de contenidos", + "Table of Contents":"Tabla de Contenidos", + "restart presentation":"Reiniciar presentación", + "restart?":"Inicio" + }; + +strings_es[helpText] = + "Utilice el ratón, barra espaciadora, teclas Izda/Dcha, " + + "o Re pág y Av pág. Use S y B para cambiar el tamaño de fuente."; + +var strings_ca = { + "slide":"pàg..", + "help?":"Ajuda", + "contents?":"Índex", + "table of contents":"taula de continguts", + "Table of Contents":"Taula de Continguts", + "restart presentation":"Reiniciar presentació", + "restart?":"Inici" + }; + +strings_ca[helpText] = + "Utilitzi el ratolí, barra espaiadora, tecles Esq./Dta. " + + "o Re pàg y Av pàg. Usi S i B per canviar grandària de font."; + +var strings_nl = { + "slide":"pagina", + "help?":"Help?", + "contents?":"Inhoud?", + "table of contents":"inhoudsopgave", + "Table of Contents":"Inhoudsopgave", + "restart presentation":"herstart presentatie", + "restart?":"Herstart?" + }; + +strings_nl[helpText] = + "Navigeer d.m.v. het muis, spatiebar, Links/Rechts toetsen, " + + "of PgUp en PgDn. Gebruik S en B om de karaktergrootte te veranderen."; + +var strings_de = { + "slide":"Seite", + "help?":"Hilfe", + "contents?":"Übersicht", + "table of contents":"Inhaltsverzeichnis", + "Table of Contents":"Inhaltsverzeichnis", + "restart presentation":"Präsentation neu starten", + "restart?":"Neustart" + }; + +strings_de[helpText] = + "Benutzen Sie die Maus, Leerschlag, die Cursortasten links/rechts oder " + + "Page up/Page Down zum Wechseln der Seiten und S und B für die Schriftgrösse."; + +var strings_pl = { + "slide":"slajd", + "help?":"pomoc?", + "contents?":"spis treści?", + "table of contents":"spis treści", + "Table of Contents":"Spis Treści", + "restart presentation":"Restartuj prezentację", + "restart?":"restart?" + }; + +strings_pl[helpText] = + "Zmieniaj slajdy klikając myszą, naciskając spację, strzałki lewo/prawo" + + "lub PgUp / PgDn. Użyj klawiszy S i B, aby zmienić rozmiar czczionki."; + +var strings_fr = { + "slide":"page", + "help?":"Aide", + "contents?":"Index", + "table of contents":"table des matières", + "Table of Contents":"Table des matières", + "restart presentation":"Recommencer l'exposé", + "restart?":"Début" + }; + +strings_fr[helpText] = + "Naviguez avec la souris, la barre d'espace, les flèches " + + "gauche/droite ou les touches Pg Up, Pg Dn. Utilisez " + + "les touches S et B pour modifier la taille de la police."; + +var strings_hu = { + "slide":"oldal", + "help?":"segítség", + "contents?":"tartalom", + "table of contents":"tartalomjegyzék", + "Table of Contents":"Tartalomjegyzék", + "restart presentation":"bemutató újraindítása", + "restart?":"újraindítás" + }; + +strings_hu[helpText] = + "Az oldalak közti lépkedéshez kattintson az egérrel, vagy " + + "használja a szóköz, a bal, vagy a jobb nyíl, illetve a Page Down, " + + "Page Up billentyűket. Az S és a B billentyűkkel változtathatja " + + "a szöveg méretét."; + +var strings_it = { + "slide":"pag.", + "help?":"Aiuto", + "contents?":"Indice", + "table of contents":"indice", + "Table of Contents":"Indice", + "restart presentation":"Ricominciare la presentazione", + "restart?":"Inizio" + }; + +strings_it[helpText] = + "Navigare con mouse, barra spazio, frecce sinistra/destra o " + + "PgUp e PgDn. Usare S e B per cambiare la dimensione dei caratteri."; + +var strings_el = { + "slide":"σελίδα", + "help?":"βοήθεια;", + "contents?":"περιεχόμενα;", + "table of contents":"πίνακας περιεχομένων", + "Table of Contents":"Πίνακας Περιεχομένων", + "restart presentation":"επανεκκίνηση παρουσίασης", + "restart?":"επανεκκίνηση;" + }; + +strings_el[helpText] = + "Πλοηγηθείτε με το κλίκ του ποντικιού, το space, τα βέλη αριστερά/δεξιά, " + + "ή Page Up και Page Down. Χρησιμοποιήστε τα πλήκτρα S και B για να αλλάξετε " + + "το μέγεθος της γραμματοσειράς."; + +var strings_ja = { + "slide":"スライド", + "help?":"ヘルプ", + "contents?":"目次", + "table of contents":"目次を表示", + "Table of Contents":"目次", + "restart presentation":"最初から再生", + "restart?":"最初から" +}; + +strings_ja[helpText] = + "マウス左クリック ・ スペース ・ 左右キー " + + "または Page Up ・ Page Downで操作， S ・ Bでフォントサイズ変更"; + +var strings_zh = { + "slide":"幻灯片", + "help?":"帮助?", + "contents?":"内容?", + "table of contents":"目录", + "Table of Contents":"目录", + "restart presentation":"重新启动展示", + "restart?":"重新启动?" +}; + +strings_zh[helpText] = + "用鼠标点击, 空格条, 左右箭头, Pg Up 和 Pg Dn 导航. " + + "用 S, B 改变字体大小."; + +var strings_ru = { + "slide":"слайд", + "help?":"помощь?", + "contents?":"содержание?", + "table of contents":"оглавление", + "Table of Contents":"Оглавление", + "restart presentation":"перезапустить презентацию", + "restart?":"перезапуск?" + }; + +strings_ru[helpText] = + "Перемещайтесь кликая мышкой, используя клавишу пробел, стрелки" + + "влево/вправо или Pg Up и Pg Dn. Клавиши S и B меняют размер шрифта."; + + +// each such language array is declared in the localize array +// used indirectly as in help.innerHTML = "help".localize(); +var localize = { + "es":strings_es, + "ca":strings_ca, + "nl":strings_nl, + "de":strings_de, + "pl":strings_pl, + "fr":strings_fr, + "hu":strings_hu, + "it":strings_it, + "el":strings_el, + "jp":strings_ja, + "zh":strings_zh, + "ru":strings_ru + }; + +/* general initialization */ +function startup() +{ + if (slidy_started) + { + alert("already started"); + return; + } + slidy_started = true; + + // find human language from html element + // for use in localizing strings + lang = document.body.parentNode.getAttribute("lang"); + + if (!lang) + lang = document.body.parentNode.getAttribute("xml:lang"); + + if (!lang) + lang = "en"; + + document.body.style.visibility = "visible"; + title = document.title; + toolbar = addToolbar(); + wrapImplicitSlides(); + slides = collectSlides(); + notes = collectNotes(); + objects = document.body.getElementsByTagName("object"); + backgrounds = collectBackgrounds(); + patchAnchors(); + + slidenum = findSlideNumber(location.href); + window.offscreenbuffering = true; + sizeAdjustment = findSizeAdjust(); + hideImageToolbar(); // suppress IE image toolbar popup + initOutliner(); // activate fold/unfold support + + if (slides.length > 0) + { + var slide = slides[slidenum]; + slide.style.position = "absolute"; + + if (slidenum > 0) + { + setVisibilityAllIncremental("visible"); + lastShown = previousIncrementalItem(null); + setEosStatus(true); + } + else + { + lastShown = null; + setVisibilityAllIncremental("hidden"); + setEosStatus(!nextIncrementalItem(lastShown)); + } + + setLocation(); + } + + toc = tableOfContents(); + hideTableOfContents(); + + // bind event handlers + document.onclick = mouseButtonClick; + document.onmouseup = mouseButtonUp; + document.onkeydown = keyDown; + window.onresize = resized; + window.onscroll = scrolled; + window.onunload = unloaded; + singleSlideView(); + + + setLocation(); + resized(); + + if (ie7) + setTimeout("ieHack()", 100); + + showToolbar(); + setInterval("checkLocation()", 200); // for back button detection +} + +// add localize method to all strings for use +// as in help.innerHTML = "help".localize(); +String.prototype.localize = function() +{ + if (this == "") + return this; + + // try full language code, e.g. en-US + var s, lookup = localize[lang]; + + if (lookup) + { + s = lookup[this]; + + if (s) + return s; + } + + // try en if undefined for en-US + var lg = lang.split("-"); + + if (lg.length > 1) + { + lookup = localize[lg[0]]; + + if (lookup) + { + s = lookup[this]; + + if (s) + return s; + } + } + + // otherwise string as is + return this; +} + +// suppress IE's image toolbar pop up +function hideImageToolbar() +{ + if (!ns_pos) + { + var images = document.getElementsByTagName("IMG"); + + for (var i = 0; i < images.length; ++i) + images[i].setAttribute("galleryimg", "no"); + } +} + +// hack to persuade IE to compute correct document height +// as needed for simulating fixed positioning of toolbar +function ieHack() +{ + window.resizeBy(0,-1); + window.resizeBy(0, 1); +} + +function unloaded(e) +{ + //alert("unloaded"); +} + +// Firefox reload SVG bug work around +function reload(e) +{ + if (!e) + var e = window.event; + + hideBackgrounds(); + setTimeout("document.reload();", 100); + + stopPropagation(e); + e.cancel = true; + e.returnValue = false; + + return false; +} + +// Safari and Konqueror don't yet support getComputedStyle() +// and they always reload page when location.href is updated +function isKHTML() +{ + var agent = navigator.userAgent; + return (agent.indexOf("KHTML") >= 0 ? true : false); +} + +function resized() +{ + var width = 0; + + if ( typeof( window.innerWidth ) == 'number' ) + width = window.innerWidth; // Non IE browser + else if (document.documentElement && document.documentElement.clientWidth) + width = document.documentElement.clientWidth; // IE6 + else if (document.body && document.body.clientWidth) + width = document.body.clientWidth; // IE4 + + var height = 0; + + if ( typeof( window.innerHeight ) == 'number' ) + height = window.innerHeight; // Non IE browser + else if (document.documentElement && document.documentElement.clientHeight) + height = document.documentElement.clientHeight; // IE6 + else if (document.body && document.body.clientHeight) + height = document.body.clientHeight; // IE4 + + if (height && (width/height > 1.05*1024/768)) + { + width = height * 1024.0/768; + } + + // IE fires onresize even when only font size is changed! + // so we do a check to avoid blocking < and > actions + if (width != lastWidth || height != lastHeight) + { + if (width >= 1100) + sizeIndex = 5; // 4 + else if (width >= 1000) + sizeIndex = 4; // 3 + else if (width >= 800) + sizeIndex = 3; // 2 + else if (width >= 600) + sizeIndex = 2; // 1 + else if (width) + sizeIndex = 0; + + // add in font size adjustment from meta element e.g. + // <meta name="font-size-adjustment" content="-2" /> + // useful when slides have too much content ;-) + + if (0 <= sizeIndex + sizeAdjustment && + sizeIndex + sizeAdjustment < sizes.length) + sizeIndex = sizeIndex + sizeAdjustment; + + // enables cross browser use of relative width/height + // on object elements for use with SVG and Flash media + adjustObjectDimensions(width, height); + + document.body.style.fontSize = sizes[sizeIndex]; + + lastWidth = width; + lastHeight = height; + + // force reflow to work around Mozilla bug + //if (ns_pos) + { + var slide = slides[slidenum]; + hideSlide(slide); + showSlide(slide); + } + + // force correct positioning of toolbar + refreshToolbar(200); + } +} + +function scrolled() +{ + if (toolbar && !ns_pos && !ie7) + { + hackoffset = scrollXOffset(); + // hide toolbar + toolbar.style.display = "none"; + + // make it reappear later + if (scrollhack == 0 && !viewAll) + { + setTimeout(showToolbar, 1000); + scrollhack = 1; + } + } +} + +// used to ensure IE refreshes toolbar in correct position +function refreshToolbar(interval) +{ + if (!ns_pos && !ie7) + { + hideToolbar(); + setTimeout(showToolbar, interval); + } +} + +// restores toolbar after short delay +function showToolbar() +{ + if (wantToolbar) + { + if (!ns_pos) + { + // adjust position to allow for scrolling + var xoffset = scrollXOffset(); + toolbar.style.left = xoffset; + toolbar.style.right = xoffset; + + // determine vertical scroll offset + //var yoffset = scrollYOffset(); + + // bottom is doc height - window height - scroll offset + //var bottom = documentHeight() - lastHeight - yoffset + + //if (yoffset > 0 || documentHeight() > lastHeight) + // bottom += 16; // allow for height of scrollbar + + toolbar.style.bottom = 0; //bottom; + } + + toolbar.style.display = "block"; + toolbar.style.visibility = "visible"; + } + + scrollhack = 0; + + + // set the keyboard focus to the help link on the + // toolbar to ensure that document has the focus + // IE doesn't always work with window.focus() + // and this hack has benefit of Enter for help + + try + { + if (!opera) + helpAnchor.focus(); + } + catch (e) + { + } +} + +function hideToolbar() +{ + toolbar.style.display = "none"; + toolbar.style.visibility = "hidden"; + window.focus(); +} + +// invoked via F key +function toggleToolbar() +{ + if (!viewAll) + { + if (toolbar.style.display == "none") + { + toolbar.style.display = "block"; + toolbar.style.visibility = "visible"; + wantToolbar = 1; + } + else + { + toolbar.style.display = "none"; + toolbar.style.visibility = "hidden"; + wantToolbar = 0; + } + } +} + +function scrollXOffset() +{ + if (window.pageXOffset) + return self.pageXOffset; + + if (document.documentElement && + document.documentElement.scrollLeft) + return document.documentElement.scrollLeft; + + if (document.body) + return document.body.scrollLeft; + + return 0; +} + + +function scrollYOffset() +{ + if (window.pageYOffset) + return self.pageYOffset; + + if (document.documentElement && + document.documentElement.scrollTop) + return document.documentElement.scrollTop; + + if (document.body) + return document.body.scrollTop; + + return 0; +} + +// looking for a way to determine height of slide content +// the slide itself is set to the height of the window +function optimizeFontSize() +{ + var slide = slides[slidenum]; + + //var dh = documentHeight(); //getDocHeight(document); + var dh = slide.scrollHeight; + var wh = getWindowHeight(); + var u = 100 * dh / wh; + + alert("window utilization = " + u + "% (doc " + + dh + " win " + wh + ")"); +} + +function getDocHeight(doc) // from document object +{ + if (!doc) + doc = document; + + if (doc && doc.body && doc.body.offsetHeight) + return doc.body.offsetHeight; // ns/gecko syntax + + if (doc && doc.body && doc.body.scrollHeight) + return doc.body.scrollHeight; + + alert("couldn't determine document height"); +} + +function getWindowHeight() +{ + if ( typeof( window.innerHeight ) == 'number' ) + return window.innerHeight; // Non IE browser + + if (document.documentElement && document.documentElement.clientHeight) + return document.documentElement.clientHeight; // IE6 + + if (document.body && document.body.clientHeight) + return document.body.clientHeight; // IE4 +} + + + +function documentHeight() +{ + var sh, oh; + + sh = document.body.scrollHeight; + oh = document.body.offsetHeight; + + if (sh && oh) + { + return (sh > oh ? sh : oh); + } + + // no idea! + return 0; +} + +function smaller() +{ + if (sizeIndex > 0) + { + --sizeIndex; + } + + toolbar.style.display = "none"; + document.body.style.fontSize = sizes[sizeIndex]; + var slide = slides[slidenum]; + hideSlide(slide); + showSlide(slide); + setTimeout(showToolbar, 300); +} + +function bigger() +{ + if (sizeIndex < sizes.length - 1) + { + ++sizeIndex; + } + + toolbar.style.display = "none"; + document.body.style.fontSize = sizes[sizeIndex]; + var slide = slides[slidenum]; + hideSlide(slide); + showSlide(slide); + setTimeout(showToolbar, 300); +} + +// enables cross browser use of relative width/height +// on object elements for use with SVG and Flash media +// with thanks to Ivan Herman for the suggestion +function adjustObjectDimensions(width, height) +{ + for( var i = 0; i < objects.length; i++ ) + { + var obj = objects[i]; + var mimeType = obj.getAttribute("type"); + + if (mimeType == "image/svg+xml" || mimeType == "application/x-shockwave-flash") + { + if ( !obj.initialWidth ) + obj.initialWidth = obj.getAttribute("width"); + + if ( !obj.initialHeight ) + obj.initialHeight = obj.getAttribute("height"); + + if ( obj.initialWidth && obj.initialWidth.charAt(obj.initialWidth.length-1) == "%" ) + { + var w = parseInt(obj.initialWidth.slice(0, obj.initialWidth.length-1)); + var newW = width * (w/100.0); + obj.setAttribute("width",newW); + } + + if ( obj.initialHeight && obj.initialHeight.charAt(obj.initialHeight.length-1) == "%" ) + { + var h = parseInt(obj.initialHeight.slice(0, obj.initialHeight.length-1)); + var newH = height * (h/100.0); + obj.setAttribute("height", newH); + } + } + } +} + +function cancel(event) +{ + if (event) + { + event.cancel = true; + event.returnValue = false; + + if (event.preventDefault) + event.preventDefault(); + } + + return false; +} + +// See e.g. http://www.quirksmode.org/js/events/keys.html for keycodes +function keyDown(event) +{ + var key; + + if (!event) + var event = window.event; + + // kludge around NS/IE differences + if (window.event) + key = window.event.keyCode; + else if (event.which) + key = event.which; + else + return true; // Yikes! unknown browser + + // ignore event if key value is zero + // as for alt on Opera and Konqueror + if (!key) + return true; + + // check for concurrent control/command/alt key + // but are these only present on mouse events? + + if (event.ctrlKey || event.altKey || event.metaKey) + return true; + + // dismiss table of contents if visible + if (isShownToc() && key != 9 && key != 16 && key != 38 && key != 40) + { + hideTableOfContents(); + + if (key == 27 || key == 84 || key == 67) + return cancel(event); + } + + if (key == 34) // Page Down + { + if (viewAll) + return true; + + nextSlide(false); + return cancel(event); + } + else if (key == 33) // Page Up + { + if (viewAll) + return true; + + previousSlide(false); + return cancel(event); + } + else if (key == 32) // space bar + { + nextSlide(true); + return cancel(event); + } + else if (key == 37) // Left arrow + { + previousSlide(!event.shiftKey); + return cancel(event); + } + else if (key == 36) // Home + { + firstSlide(); + return cancel(event); + } + else if (key == 35) // End + { + lastSlide(); + return cancel(event); + } + else if (key == 39) // Right arrow + { + nextSlide(!event.shiftKey); + return cancel(event); + } + else if (key == 13) // Enter + { + if (outline) + { + if (outline.visible) + fold(outline); + else + unfold(outline); + + return cancel(event); + } + } + else if (key == 188) // < for smaller fonts + { + smaller(); + return cancel(event); + } + else if (key == 190) // > for larger fonts + { + bigger(); + return cancel(event); + } + else if (key == 189 || key == 109) // - for smaller fonts + { + smaller(); + return cancel(event); + } + else if (key == 187 || key == 191 || key == 107) // = + for larger fonts + { + bigger(); + return cancel(event); + } + else if (key == 83) // S for smaller fonts + { + smaller(); + return cancel(event); + } + else if (key == 66) // B for larger fonts + { + bigger(); + return cancel(event); + } + else if (key == 90) // Z for last slide + { + lastSlide(); + return cancel(event); + } + else if (key == 70) // F for toggle toolbar + { + toggleToolbar(); + return cancel(event); + } + else if (key == 65) // A for toggle view single/all slides + { + toggleView(); + return cancel(event); + } + else if (key == 75) // toggle action of left click for next page + { + // commented out by kent 20100210. + /* + mouseClickEnabled = !mouseClickEnabled; + alert((mouseClickEnabled ? "enabled" : "disabled") + " mouse click advance"); + return cancel(event); + */ + } + else if (key == 84 || key == 67) // T or C for table of contents + { + if (toc) + showTableOfContents(); + + return cancel(event); + } + else if (key == 72) // H for help + { + window.location = helpPage; + return cancel(event); + } + + // added by kent 20100210 + else if (key == 77) { + showspeak = !showspeak; + var value = (showspeak? "visible":"hidden"); + var elems = document.getElementsByClassName("speak"); + + for (var i=0; i<elems.length; i++) { + elems[i].style.visibility = value; + } + return cancel(event); + } + + //else if (key == 93) // Windows menu key + //alert("lastShown is " + lastShown); + //else alert("key code is "+ key); + + + return true; +} + +// make note of length of selected text +// as this evaluates to zero in click event +function mouseButtonUp(e) +{ + selectedTextLen = getSelectedText().length; +} + +// right mouse button click is reserved for context menus +// it is more reliable to detect rightclick than leftclick +function mouseButtonClick(e) +{ + var rightclick = false; + var leftclick = false; + var middleclick = false; + var target; + + if (!e) + var e = window.event; + + if (e.target) + target = e.target; + else if (e.srcElement) + target = e.srcElement; + + // work around Safari bug + if (target.nodeType == 3) + target = target.parentNode; + + if (e.which) // all browsers except IE + { + leftclick = (e.which == 1); + middleclick = (e.which == 2); + rightclick = (e.which == 3); + } + else if (e.button) + { + // Konqueror gives 1 for left, 4 for middle + // IE6 gives 0 for left and not 1 as I expected + + if (e.button == 4) + middleclick = true; + + // all browsers agree on 2 for right button + rightclick = (e.button == 2); + } + else leftclick = true; + + //alert("selected text length = "+selectedTextLen); + + if (selectedTextLen > 0) + { + stopPropagation(e); + e.cancel = true; + e.returnValue = false; + return false; + } + + // dismiss table of contents + hideTableOfContents(); + + // check if target is something that probably want's clicks + // e.g. embed, object, input, textarea, select, option + + if (mouseClickEnabled && leftclick && + target.nodeName != "EMBED" && + target.nodeName != "OBJECT" && + target.nodeName != "VIDEO" && + target.nodeName != "INPUT" && + target.nodeName != "TEXTAREA" && + target.nodeName != "SELECT" && + target.nodeName != "OPTION") + { + nextSlide(true); + stopPropagation(e); + e.cancel = true; + e.returnValue = false; + } +} + +function previousSlide(incremental) +{ + if (!viewAll) + { + var slide; + + if ((incremental || slidenum == 0) && lastShown != null) + { + lastShown = hidePreviousItem(lastShown); + setEosStatus(false); + } + else if (slidenum > 0) + { + slide = slides[slidenum]; + hideSlide(slide); + + slidenum = slidenum - 1; + slide = slides[slidenum]; + setVisibilityAllIncremental("visible"); + lastShown = previousIncrementalItem(null); + setEosStatus(true); + showSlide(slide); + } + + setLocation(); + + if (!ns_pos) + refreshToolbar(200); + } +} + +function nextSlide(incremental) +{ + if (!viewAll) + { + var slide, last = lastShown; + + if (incremental || slidenum == slides.length - 1) + lastShown = revealNextItem(lastShown); + + if ((!incremental || lastShown == null) && slidenum < slides.length - 1) + { + slide = slides[slidenum]; + hideSlide(slide); + + slidenum = slidenum + 1; + slide = slides[slidenum]; + lastShown = null; + setVisibilityAllIncremental("hidden"); + showSlide(slide); + } + else if (!lastShown) + { + if (last && incremental) + lastShown = last; + } + + setLocation(); + + setEosStatus(!nextIncrementalItem(lastShown)); + + if (!ns_pos) + refreshToolbar(200); + } +} + +// to first slide with nothing revealed +// i.e. state at start of presentation +function firstSlide() +{ + if (!viewAll) + { + var slide; + + if (slidenum != 0) + { + slide = slides[slidenum]; + hideSlide(slide); + + slidenum = 0; + slide = slides[slidenum]; + lastShown = null; + setVisibilityAllIncremental("hidden"); + showSlide(slide); + } + + setEosStatus(!nextIncrementalItem(lastShown)); + setLocation(); + } +} + + +// to last slide with everything revealed +// i.e. state at end of presentation +function lastSlide() +{ + if (!viewAll) + { + var slide; + + lastShown = null; //revealNextItem(lastShown); + + if (lastShown == null && slidenum < slides.length - 1) + { + slide = slides[slidenum]; + hideSlide(slide); + slidenum = slides.length - 1; + slide = slides[slidenum]; + setVisibilityAllIncremental("visible"); + lastShown = previousIncrementalItem(null); + + showSlide(slide); + } + else + { + setVisibilityAllIncremental("visible"); + lastShown = previousIncrementalItem(null); + } + + setEosStatus(true); + setLocation(); + } +} + +// first slide is 0 +function gotoSlide(num) +{ + //alert("going to slide " + (num+1)); + var slide = slides[slidenum]; + hideSlide(slide); + slidenum = num; + slide = slides[slidenum]; + lastShown = null; + setVisibilityAllIncremental("hidden"); + setEosStatus(!nextIncrementalItem(lastShown)); + document.title = title + " (" + (slidenum+1) + ")"; + showSlide(slide); + showSlideNumber(); +} + +function setEosStatus(state) +{ + if (eos) + eos.style.color = (state ? "rgb(240,240,240)" : "red"); +} + +function showSlide(slide) +{ + syncBackground(slide); + window.scrollTo(0,0); + slide.style.visibility = "visible"; + slide.style.display = "block"; +} + +function hideSlide(slide) +{ + slide.style.visibility = "hidden"; + slide.style.display = "none"; +} + +function beforePrint() +{ + showAllSlides(); + hideToolbar(); +} + +function afterPrint() +{ + if (!viewAll) + { + singleSlideView(); + showToolbar(); + } +} + +function printSlides() +{ + beforePrint(); + window.print(); + afterPrint(); +} + +function toggleView() +{ + if (viewAll) + { + singleSlideView(); + showToolbar(); + viewAll = 0; + } + else + { + showAllSlides(); + hideToolbar(); + viewAll = 1; + } +} + +// prepare for printing +function showAllSlides() +{ + var slide; + + for (var i = 0; i < slides.length; ++i) + { + slide = slides[i]; + + slide.style.position = "relative"; + slide.style.borderTopStyle = "solid"; + slide.style.borderTopWidth = "thin"; + slide.style.borderTopColor = "black"; + + try { + if (i == 0) + slide.style.pageBreakBefore = "avoid"; + else + slide.style.pageBreakBefore = "always"; + } + catch (e) + { + //do nothing + } + + setVisibilityAllIncremental("visible"); + showSlide(slide); + } + + var note; + + for (var i = 0; i < notes.length; ++i) + { + showSlide(notes[i]); + } + + // no easy way to render background under each slide + // without duplicating the background divs for each slide + // therefore hide backgrounds to avoid messing up slides + hideBackgrounds(); +} + +// restore after printing +function singleSlideView() +{ + var slide; + + for (var i = 0; i < slides.length; ++i) + { + slide = slides[i]; + + slide.style.position = "absolute"; + + if (i == slidenum) + { + slide.style.borderStyle = "none"; + showSlide(slide); + } + else + { + slide.style.borderStyle = "none"; + hideSlide(slide); + } + } + + setVisibilityAllIncremental("visible"); + lastShown = previousIncrementalItem(null); + + var note; + + for (var i = 0; i < notes.length; ++i) + { + hideSlide(notes[i]); + } +} + +// the string str is a whitespace separated list of tokens +// test if str contains a particular token, e.g. "slide" +function hasToken(str, token) +{ + if (str) + { + // define pattern as regular expression + var pattern = /\w+/g; + + // check for matches + // place result in array + var result = str.match(pattern); + + // now check if desired token is present + for (var i = 0; i < result.length; i++) + { + if (result[i] == token) + return true; + } + } + + return false; +} + +function getClassList(element) +{ + if (typeof element.className != 'undefined') + return element.className; + + var clsname = (ns_pos||ie8) ? "class" : "className"; + return element.getAttribute(clsname); +} + +function hasClass(element, name) +{ + var regexp = new RegExp("(^| )" + name + "\W*"); + + if (typeof element.className != 'undefined') + return regexp.test(element.className); + + var clsname = (ns_pos||ie8) ? "class" : "className"; + return regexp.test(element.getAttribute(clsname)); +} + +function removeClass(element, name) +{ + var regexp = new RegExp("(^| )" + name + "\W*"); + var clsval = ""; + + if (typeof element.className != 'undefined') + { + clsval = element.className; + + if (clsval) + { + clsval = clsval.replace(regexp, ""); + element.className = clsval; + } + } + else + { + var clsname = (ns_pos||ie8) ? "class" : "className"; + clsval = element.getAttribute(clsname); + + if (clsval) + { + clsval = clsval.replace(regexp, ""); + element.setAttribute(clsname, clsval); + } + } +} + +function addClass(element, name) +{ + if (!hasClass(element, name)) + { + if (typeof element.className != 'undefined') + element.className += " " + name; + else + { + var clsname = (ns_pos||ie8) ? "class" : "className"; + var clsval = element.getAttribute(clsname); + clsval = clsval ? clsval + " " + name : name; + element.setAttribute(clsname, clsval); + } + } +} + +// wysiwyg editors make it hard to use div elements +// e.g. amaya loses the div when you copy and paste +// this function wraps div elements around implicit +// slides which start with an h1 element and continue +// up to the next heading or div element +function wrapImplicitSlides() +{ + var i, heading, node, next, div; + var headings = document.getElementsByTagName("h1"); + + if (!headings) + return; + + for (i = 0; i < headings.length; ++i) + { + heading = headings[i]; + + if (heading.parentNode != document.body) + continue; + + node = heading.nextSibling; + + div = document.createElement("div"); + addClass(div, "slide"); + document.body.replaceChild(div, heading); + div.appendChild(heading); + + while (node) + { + if (node.nodeType == 1 && // an element + (node.nodeName == "H1" || + node.nodeName == "h1" || + node.nodeName == "DIV" || + node.nodeName == "div")) + break; + + next = node.nextSibling; + node = document.body.removeChild(node); + div.appendChild(node); + node = next; + } + } +} + +// return new array of all slides +function collectSlides() +{ + var slides = new Array(); + var divs = document.body.getElementsByTagName("div"); + + for (var i = 0; i < divs.length; ++i) + { + div = divs.item(i); + + if (hasClass(div, "slide")) + { + // add slide to collection + slides[slides.length] = div; + + // hide each slide as it is found + div.style.display = "none"; + div.style.visibility = "hidden"; + + // add dummy <br/> at end for scrolling hack + var node1 = document.createElement("br"); + div.appendChild(node1); + var node2 = document.createElement("br"); + div.appendChild(node2); + } + else if (hasClass(div, "background")) + { // work around for Firefox SVG reload bug + // which otherwise replaces 1st SVG graphic with 2nd + div.style.display = "block"; + } + } + + return slides; +} + +// return new array of all <div class="handout"> +function collectNotes() +{ + var notes = new Array(); + var divs = document.body.getElementsByTagName("div"); + + for (var i = 0; i < divs.length; ++i) + { + div = divs.item(i); + + if (hasClass(div, "handout")) + { + // add slide to collection + notes[notes.length] = div; + + // hide handout notes as they are found + div.style.display = "none"; + div.style.visibility = "hidden"; + } + } + + return notes; +} + +// return new array of all <div class="background"> +// including named backgrounds e.g. class="background titlepage" +function collectBackgrounds() +{ + var backgrounds = new Array(); + var divs = document.body.getElementsByTagName("div"); + + for (var i = 0; i < divs.length; ++i) + { + div = divs.item(i); + + if (hasClass(div, "background")) + { + // add slide to collection + backgrounds[backgrounds.length] = div; + + // hide named backgrounds as they are found + // e.g. class="background epilog" + if (getClassList(div) != "background") + { + div.style.display = "none"; + div.style.visibility = "hidden"; + } + } + } + + return backgrounds; +} + +// show just the backgrounds pertinent to this slide +function syncBackground(slide) +{ + var background; + var bgColor; + + if (slide.currentStyle) + bgColor = slide.currentStyle["backgroundColor"]; + else if (document.defaultView) + { + var styles = document.defaultView.getComputedStyle(slide,null); + + if (styles) + bgColor = styles.getPropertyValue("background-color"); + else // broken implementation probably due Safari or Konqueror + { + //alert("defective implementation of getComputedStyle()"); + bgColor = "transparent"; + } + } + else + bgColor == "transparent"; + + if (bgColor == "transparent") + { + var slideClass = getClassList(slide); + + for (var i = 0; i < backgrounds.length; i++) + { + background = backgrounds[i]; + + var bgClass = getClassList(background); + + if (matchingBackground(slideClass, bgClass)) + { + background.style.display = "block"; + background.style.visibility = "visible"; + } + else + { + background.style.display = "none"; + background.style.visibility = "hidden"; + } + } + } + else // forcibly hide all backgrounds + hideBackgrounds(); +} + +function hideBackgrounds() +{ + for (var i = 0; i < backgrounds.length; i++) + { + background = backgrounds[i]; + background.style.display = "none"; + background.style.visibility = "hidden"; + } +} + +// compare classes for slide and background +function matchingBackground(slideClass, bgClass) +{ + if (bgClass == "background") + return true; + + // define pattern as regular expression + var pattern = /\w+/g; + + // check for matches and place result in array + var result = slideClass.match(pattern); + + // now check if desired name is present for background + for (var i = 0; i < result.length; i++) + { + if (hasToken(bgClass, result[i])) + return true; + } + + return false; +} + +// left to right traversal of root's content +function nextNode(root, node) +{ + if (node == null) + return root.firstChild; + + if (node.firstChild) + return node.firstChild; + + if (node.nextSibling) + return node.nextSibling; + + for (;;) + { + node = node.parentNode; + + if (!node || node == root) + break; + + if (node && node.nextSibling) + return node.nextSibling; + } + + return null; +} + +// right to left traversal of root's content +function previousNode(root, node) +{ + if (node == null) + { + node = root.lastChild; + + if (node) + { + while (node.lastChild) + node = node.lastChild; + } + + return node; + } + + if (node.previousSibling) + { + node = node.previousSibling; + + while (node.lastChild) + node = node.lastChild; + + return node; + } + + if (node.parentNode != root) + return node.parentNode; + + return null; +} + +// HTML elements that can be used with class="incremental" +// note that you can also put the class on containers like +// up, ol, dl, and div to make their contents appear +// incrementally. Upper case is used since this is what +// browsers report for HTML node names (text/html). +function incrementalElementList() +{ + var inclist = new Array(); + inclist["P"] = true; + inclist["PRE"] = true; + inclist["LI"] = true; + inclist["BLOCKQUOTE"] = true; + inclist["DT"] = true; + inclist["DD"] = true; + inclist["H2"] = true; + inclist["H3"] = true; + inclist["H4"] = true; + inclist["H5"] = true; + inclist["H6"] = true; + inclist["SPAN"] = true; + inclist["ADDRESS"] = true; + inclist["TABLE"] = true; + inclist["TR"] = true; + inclist["TH"] = true; + inclist["TD"] = true; + inclist["IMG"] = true; + inclist["OBJECT"] = true; + return inclist; +} + +function nextIncrementalItem(node) +{ + var slide = slides[slidenum]; + + for (;;) + { + node = nextNode(slide, node); + + if (node == null || node.parentNode == null) + break; + + if (node.nodeType == 1) // ELEMENT + { + if (node.nodeName == "BR") + continue; + + if (hasClass(node, "incremental") + && okayForIncremental[node.nodeName]) + return node; + + if (hasClass(node.parentNode, "incremental") + && !hasClass(node, "non-incremental")) + return node; + } + } + + return node; +} + +function previousIncrementalItem(node) +{ + var slide = slides[slidenum]; + + for (;;) + { + node = previousNode(slide, node); + + if (node == null || node.parentNode == null) + break; + + if (node.nodeType == 1) + { + if (node.nodeName == "BR") + continue; + + if (hasClass(node, "incremental") + && okayForIncremental[node.nodeName]) + return node; + + if (hasClass(node.parentNode, "incremental") + && !hasClass(node, "non-incremental")) + return node; + } + } + + return node; +} + +// set visibility for all elements on current slide with +// a parent element with attribute class="incremental" +function setVisibilityAllIncremental(value) +{ + var node = nextIncrementalItem(null); + + while (node) + { + node.style.visibility = value; + node = nextIncrementalItem(node); + } +} + +// reveal the next hidden item on the slide +// node is null or the node that was last revealed +function revealNextItem(node) +{ + node = nextIncrementalItem(node); + + if (node && node.nodeType == 1) // an element + node.style.visibility = "visible"; + + return node; +} + + +// exact inverse of revealNextItem(node) +function hidePreviousItem(node) +{ + if (node && node.nodeType == 1) // an element + node.style.visibility = "hidden"; + + return previousIncrementalItem(node); +} + + +/* set click handlers on all anchors */ +function patchAnchors() +{ + var anchors = document.body.getElementsByTagName("a"); + + for (var i = 0; i < anchors.length; ++i) + { + anchors[i].onclick = clickedAnchor; + } +} + +function clickedAnchor(e) +{ + if (!e) + var e = window.event; + + // compare this.href with location.href + // for link to another slide in this doc + + if (pageAddress(this.href) == pageAddress(location.href)) + { + // yes, so find new slide number + var newslidenum = findSlideNumber(this.href); + + if (newslidenum != slidenum) + { + slide = slides[slidenum]; + hideSlide(slide); + slidenum = newslidenum; + slide = slides[slidenum]; + showSlide(slide); + setLocation(); + } + } + else if (this.target == null) + location.href = this.href; + + this.blur(); + stopPropagation(e); +} + +function pageAddress(uri) +{ + var i = uri.indexOf("#"); + + if (i < 0) + i = uri.indexOf("%23"); + + // check if anchor is entire page + + if (i < 0) + return uri; // yes + + return uri.substr(0, i); +} + +function showSlideNumber() +{ + slideNumElement.innerHTML = "slide".localize() + " " + + (slidenum + 1) + "/" + slides.length; +} + +// every 200mS check if the location has been changed as a +// result of the user activating the Back button/menu item +// doesn't work for Opera < 9.5 +function checkLocation() +{ + var hash = location.hash; + + if (slidenum > 0 && (hash == "" || hash == "#")) + gotoSlide(0); + else if (hash.length > 2 && hash != "#("+(slidenum+1)+")") + { + var num = parseInt(location.hash.substr(2)); + + if (!isNaN(num)) + gotoSlide(num-1); + } +} + +// this doesn't push location onto history stack for IE +// for which a hidden iframe hack is needed: load page into +// the iframe with script that set's parent's location.hash +// but that won't work for standalone use unless we can +// create the page dynamically via a javascript: URL +function setLocation() +{ + var uri = pageAddress(location.href); + var hash = "#(" + (slidenum+1) + ")"; + + if (slidenum >= 0) + uri = uri + hash; + + if (ie && !ie8) + pushHash(hash); + + if (uri != location.href /*&& !khtml */) + location.href = uri; + + if (khtml) + hash = "(" + (slidenum+1) + ")"; + + if (!ie && location.hash != hash && location.hash != "") + location.hash = hash; + + document.title = title + " (" + (slidenum+1) + ")"; + showSlideNumber(); +} + +// only used for IE6 and IE7 +function onFrameLoaded(hash) +{ + location.hash = hash; + var uri = pageAddress(location.href); + location.href = uri + hash; +} + +// history hack with thanks to Bertrand Le Roy +function pushHash(hash) +{ + if (hash == "") hash = "#(1)"; + window.location.hash = hash; + var doc = document.getElementById("historyFrame").contentWindow.document; + doc.open("javascript:'<html></html>'"); + doc.write("<html><head><script type=\"text/javascript\">parent.onFrameLoaded('"+ + (hash) + "');</script></head><body>hello mum</body></html>"); + doc.close(); +} + +// find current slide based upon location +// first find target anchor and then look +// for associated div element enclosing it +// finally map that to slide number +function findSlideNumber(uri) +{ + // first get anchor from page location + + var i = uri.indexOf("#"); + + // check if anchor is entire page + + if (i < 0) + return 0; // yes + + var anchor = unescape(uri.substr(i+1)); + + // now use anchor as XML ID to find target + var target = document.getElementById(anchor); + + if (!target) + { + // does anchor look like "(2)" for slide 2 ?? + // where first slide is (1) + var re = /\((\d)+\)/; + + if (anchor.match(re)) + { + var num = parseInt(anchor.substring(1, anchor.length-1)); + + if (num > slides.length) + num = 1; + + if (--num < 0) + num = 0; + + return num; + } + + // accept [2] for backwards compatibility + re = /\[(\d)+\]/; + + if (anchor.match(re)) + { + var num = parseInt(anchor.substring(1, anchor.length-1)); + + if (num > slides.length) + num = 1; + + if (--num < 0) + num = 0; + + return num; + } + + // oh dear unknown anchor + return 0; + } + + // search for enclosing slide + + while (true) + { + // browser coerces html elements to uppercase! + if (target.nodeName.toLowerCase() == "div" && + hasClass(target, "slide")) + { + // found the slide element + break; + } + + // otherwise try parent element if any + + target = target.parentNode; + + if (!target) + { + return 0; // no luck! + } + }; + + for (i = 0; i < slides.length; ++i) + { + if (slides[i] == target) + return i; // success + } + + // oh dear still no luck + return 0; +} + +// find slide name from first h1 element +// default to document title + slide number +function slideName(index) +{ + var name = null; + var slide = slides[index]; + + var heading = findHeading(slide); + + if (heading) + name = extractText(heading); + + if (!name) + name = title + "(" + (index + 1) + ")"; + + name.replace(/\&/g, "&"); + name.replace(/\</g, "<"); + name.replace(/\>/g, ">"); + + return name; +} + +// find first h1 element in DOM tree +function findHeading(node) +{ if (!node || node.nodeType != 1) + return null; + + if (node.nodeName == "H1" || node.nodeName == "h1") + return node; + + var child = node.firstChild; + + while (child) + { + node = findHeading(child); + + if (node) + return node; + + child = child.nextSibling; + } + + return null; +} + +// recursively extract text from DOM tree +function extractText(node) +{ + if (!node) + return ""; + + // text nodes + if (node.nodeType == 3) + return node.nodeValue; + + // elements + if (node.nodeType == 1) + { + node = node.firstChild; + var text = ""; + + while (node) + { + text = text + extractText(node); + node = node.nextSibling; + } + + return text; + } + + return ""; +} + + +// find copyright text from meta element +function findCopyright() +{ + var name, content; + var meta = document.getElementsByTagName("meta"); + + for (var i = 0; i < meta.length; ++i) + { + name = meta[i].getAttribute("name"); + content = meta[i].getAttribute("content"); + + if (name == "copyright") + return content; + } + + return null; +} + +function findSizeAdjust() +{ + var name, content, offset; + var meta = document.getElementsByTagName("meta"); + + for (var i = 0; i < meta.length; ++i) + { + name = meta[i].getAttribute("name"); + content = meta[i].getAttribute("content"); + + if (name == "font-size-adjustment") + return 1 * content; + } + + return 1; +} + +function addToolbar() +{ + var slideCounter, page; + + var toolbar = createElement("div"); + toolbar.setAttribute("class", "toolbar"); + + if (ns_pos) // a reasonably behaved browser + { + var right = document.createElement("div"); + right.setAttribute("style", "float: right; text-align: right"); + + slideCounter = document.createElement("div") + slideCounter.innerHTML = "slide".localize() + " n/m"; + right.appendChild(slideCounter); + toolbar.appendChild(right); + + var left = document.createElement("div"); + left.setAttribute("style", "text-align: left"); + + // global end of slide indicator + eos = document.createElement("span"); + eos.innerHTML = "* "; + left.appendChild(eos); + + var help = document.createElement("a"); + help.setAttribute("href", helpPage); + help.setAttribute("title", helpText.localize()); + help.innerHTML = "help?".localize(); + left.appendChild(help); + helpAnchor = help; // save for focus hack + + var gap1 = document.createTextNode(" "); + left.appendChild(gap1); + + var contents = document.createElement("a"); + contents.setAttribute("href", "javascript:toggleTableOfContents()"); + contents.setAttribute("title", "table of contents".localize()); + contents.innerHTML = "contents?".localize(); + left.appendChild(contents); + + var gap2 = document.createTextNode(" "); + left.appendChild(gap2); + + var start = document.createElement("a"); + start.setAttribute("href", "javascript:firstSlide()"); + start.setAttribute("title", "restart presentation".localize()); + start.innerHTML = "restart?".localize(); +// start.setAttribute("href", "javascript:printSlides()"); +// start.setAttribute("title", "print all slides".localize()); +// start.innerHTML = "print!".localize(); + left.appendChild(start); + + var copyright = findCopyright(); + + if (copyright) + { + var span = document.createElement("span"); + span.innerHTML = copyright; + span.style.color = "black"; + span.style.marginLeft = "4em"; + left.appendChild(span); + } + + toolbar.appendChild(left); + } + else // IE so need to work around its poor CSS support + { + toolbar.style.position = (ie7 ? "fixed" : "absolute"); + toolbar.style.zIndex = "200"; + toolbar.style.width = "99.9%"; + toolbar.style.height = "1.2em"; + toolbar.style.top = "auto"; + toolbar.style.bottom = "0"; + toolbar.style.left = "0"; + toolbar.style.right = "0"; + toolbar.style.textAlign = "left"; + toolbar.style.fontSize = "60%"; + toolbar.style.color = "red"; + toolbar.borderWidth = 0; + toolbar.style.background = "rgb(240,240,240)"; + + // would like to have help text left aligned + // and page counter right aligned, floating + // div's don't work, so instead use nested + // absolutely positioned div's. + + var sp = document.createElement("span"); + sp.innerHTML = " * "; + toolbar.appendChild(sp); + eos = sp; // end of slide indicator + + var help = document.createElement("a"); + help.setAttribute("href", helpPage); + help.setAttribute("title", helpText.localize()); + help.innerHTML = "help?".localize(); + toolbar.appendChild(help); + helpAnchor = help; // save for focus hack + + var gap1 = document.createTextNode(" "); + toolbar.appendChild(gap1); + + var contents = document.createElement("a"); + contents.setAttribute("href", "javascript:toggleTableOfContents()"); + contents.setAttribute("title", "table of contents".localize()); + contents.innerHTML = "contents?".localize(); + toolbar.appendChild(contents); + + var gap2 = document.createTextNode(" "); + toolbar.appendChild(gap2); + + var start = document.createElement("a"); + start.setAttribute("href", "javascript:firstSlide()"); + start.setAttribute("title", "restart presentation".localize()); + start.innerHTML = "restart?".localize(); +// start.setAttribute("href", "javascript:printSlides()"); +// start.setAttribute("title", "print all slides".localize()); +// start.innerHTML = "print!".localize(); + toolbar.appendChild(start); + + var copyright = findCopyright(); + + if (copyright) + { + var span = document.createElement("span"); + span.innerHTML = copyright; + span.style.color = "black"; + span.style.marginLeft = "2em"; + toolbar.appendChild(span); + } + + slideCounter = document.createElement("div") + slideCounter.style.position = "absolute"; + slideCounter.style.width = "auto"; //"20%"; + slideCounter.style.height = "1.2em"; + slideCounter.style.top = "auto"; + slideCounter.style.bottom = 0; + slideCounter.style.right = "0"; + slideCounter.style.textAlign = "right"; + slideCounter.style.color = "red"; + slideCounter.style.background = "rgb(240,240,240)"; + + slideCounter.innerHTML = "slide".localize() + " n/m"; + toolbar.appendChild(slideCounter); + } + + // ensure that click isn't passed through to the page + toolbar.onclick = stopPropagation; + document.body.appendChild(toolbar); + slideNumElement = slideCounter; + setEosStatus(false); + + return toolbar; +} + +function isShownToc() +{ + if (toc && toc.style.visible == "visible") + return true; + + return false; +} + +function showTableOfContents() +{ + if (toc) + { + if (toc.style.visibility != "visible") + { + toc.style.visibility = "visible"; + toc.style.display = "block"; + toc.focus(); + + if (ie7 && slidenum == 0) + setTimeout("ieHack()", 100); + } + else + hideTableOfContents(); + } +} + +function hideTableOfContents() +{ + if (toc && toc.style.visibility != "hidden") + { + toc.style.visibility = "hidden"; + toc.style.display = "none"; + + try + { + if (!opera) + helpAnchor.focus(); + } + catch (e) + { + } + } +} + +function toggleTableOfContents() +{ + if (toc) + { + if (toc.style.visible != "visible") + showTableOfContents(); + else + hideTableOfContents(); + } +} + +// called on clicking toc entry +function gotoEntry(e) +{ + var target; + + if (!e) + var e = window.event; + + if (e.target) + target = e.target; + else if (e.srcElement) + target = e.srcElement; + + // work around Safari bug + if (target.nodeType == 3) + target = target.parentNode; + + if (target && target.nodeType == 1) + { + var uri = target.getAttribute("href"); + + if (uri) + { + //alert("going to " + uri); + var slide = slides[slidenum]; + hideSlide(slide); + slidenum = findSlideNumber(uri); + slide = slides[slidenum]; + lastShown = null; + setLocation(); + setVisibilityAllIncremental("hidden"); + setEosStatus(!nextIncrementalItem(lastShown)); + showSlide(slide); + //target.focus(); + + try + { + if (!opera) + helpAnchor.focus(); + } + catch (e) + { + } + } + } + + hideTableOfContents(e); + if (ie7) ieHack(); + stopPropagation(e); + return cancel(e); +} + +// called onkeydown for toc entry +function gotoTocEntry(event) +{ + var key; + + if (!event) + var event = window.event; + + // kludge around NS/IE differences + if (window.event) + key = window.event.keyCode; + else if (event.which) + key = event.which; + else + return true; // Yikes! unknown browser + + // ignore event if key value is zero + // as for alt on Opera and Konqueror + if (!key) + return true; + + // check for concurrent control/command/alt key + // but are these only present on mouse events? + + if (event.ctrlKey || event.altKey) + return true; + + if (key == 13) + { + var uri = this.getAttribute("href"); + + if (uri) + { + //alert("going to " + uri); + var slide = slides[slidenum]; + hideSlide(slide); + slidenum = findSlideNumber(uri); + slide = slides[slidenum]; + lastShown = null; + setLocation(); + setVisibilityAllIncremental("hidden"); + setEosStatus(!nextIncrementalItem(lastShown)); + showSlide(slide); + //target.focus(); + + try + { + if (!opera) + helpAnchor.focus(); + } + catch (e) + { + } + } + + hideTableOfContents(); + if (ie7) ieHack(); + return cancel(event); + } + + if (key == 40 && this.next) + { + this.next.focus(); + return cancel(event); + } + + if (key == 38 && this.previous) + { + this.previous.focus(); + return cancel(event); + } + + return true; +} + +function isTitleSlide(slide) +{ + return hasClass(slide, "title"); +} + +// create div element with links to each slide +function tableOfContents() +{ + var toc = document.createElement("div"); + addClass(toc, "toc"); + //toc.setAttribute("tabindex", "0"); + + var heading = document.createElement("div"); + addClass(heading, "toc-heading"); + heading.innerHTML = "Table of Contents".localize(); + + heading.style.textAlign = "center"; + heading.style.width = "100%"; + heading.style.margin = "0"; + heading.style.marginBottom = "1em"; + heading.style.borderBottomStyle = "solid"; + heading.style.borderBottomColor = "rgb(180,180,180)"; + heading.style.borderBottomWidth = "1px"; + + toc.appendChild(heading); + var previous = null; + + for (var i = 0; i < slides.length; ++i) + { + var title = hasClass(slides[i], "title"); + var num = document.createTextNode((i + 1) + ". "); + + toc.appendChild(num); + + var a = document.createElement("a"); + a.setAttribute("href", "#(" + (i+1) + ")"); + + if (title) + addClass(a, "titleslide"); + + var name = document.createTextNode(slideName(i)); + a.appendChild(name); + a.onclick = gotoEntry; + a.onkeydown = gotoTocEntry; + a.previous = previous; + + if (previous) + previous.next = a; + + toc.appendChild(a); + + if (i == 0) + toc.first = a; + + if (i < slides.length - 1) + { + var br = document.createElement("br"); + toc.appendChild(br); + } + + previous = a; + } + + toc.focus = function () { + if (this.first) + this.first.focus(); + } + + toc.onmouseup = mouseButtonUp; + + toc.onclick = function (e) { + e||(e=window.event); + + if (selectedTextLen <= 0) + hideTableOfContents(); + + stopPropagation(e); + + if (e.cancel != undefined) + e.cancel = true; + + if (e.returnValue != undefined) + e.returnValue = false; + + return false; + }; + + toc.style.position = "absolute"; + toc.style.zIndex = "300"; + toc.style.width = "60%"; + toc.style.maxWidth = "30em"; + toc.style.height = "30em"; + toc.style.overflow = "auto"; + toc.style.top = "auto"; + toc.style.right = "auto"; + toc.style.left = "4em"; + toc.style.bottom = "4em"; + toc.style.padding = "1em"; + toc.style.background = "rgb(240,240,240)"; + toc.style.borderStyle = "solid"; + toc.style.borderWidth = "2px"; + toc.style.fontSize = "60%"; + + document.body.insertBefore(toc, document.body.firstChild); + return toc; +} + +function replaceByNonBreakingSpace(str) +{ + for (var i = 0; i < str.length; ++i) + str[i] = 160; +} + + +function initOutliner() +{ + var items = document.getElementsByTagName("LI"); + + for (var i = 0; i < items.length; ++i) + { + var target = items[i]; + + if (!hasClass(target.parentNode, "outline")) + continue; + + target.onclick = outlineClick; + + if (!ns_pos) + { + target.onmouseover = hoverOutline; + target.onmouseout = unhoverOutline; + } + + if (foldable(target)) + { + target.foldable = true; + target.onfocus = function () {outline = this;}; + target.onblur = function () {outline = null;}; + + if (!target.getAttribute("tabindex")) + target.setAttribute("tabindex", "0"); + + if (hasClass(target, "expand")) + unfold(target); + else + fold(target); + } + else + { + addClass(target, "nofold"); + target.visible = true; + target.foldable = false; + } + } +} + +function foldable(item) +{ + if (!item || item.nodeType != 1) + return false; + + var node = item.firstChild; + + while (node) + { + if (node.nodeType == 1 && isBlock(node)) + return true; + + node = node.nextSibling; + } + + return false; +} + +function fold(item) +{ + if (item) + { + removeClass(item, "unfolded"); + addClass(item, "folded"); + } + + var node = item ? item.firstChild : null; + + while (node) + { + if (node.nodeType == 1 && isBlock(node)) // element + { + // note that getElementStyle won't work for Safari 1.3 + node.display = getElementStyle(node, "display", "display"); + node.style.display = "none"; + node.style.visibility = "hidden"; + } + + node = node.nextSibling; + } + + item.visible = false; +} + +function unfold(item) +{ + if (item) + { + addClass(item, "unfolded"); + removeClass(item, "folded"); + } + + var node = item ? item.firstChild : null; + + while (node) + { + if (node.nodeType == 1 && isBlock(node)) // element + { + // with fallback for Safari, see above + node.style.display = (node.display ? node.display : "block"); + node.style.visibility = "visible"; + } + + node = node.nextSibling; + } + + item.visible = true; +} + +function outlineClick(e) +{ + var rightclick = false; + var target; + + if (!e) + var e = window.event; + + if (e.target) + target = e.target; + else if (e.srcElement) + target = e.srcElement; + + // work around Safari bug + if (target.nodeType == 3) + target = target.parentNode; + + while (target && target.visible == undefined) + target = target.parentNode; + + if (!target) + return true; + + if (e.which) + rightclick = (e.which == 3); + else if (e.button) + rightclick = (e.button == 2); + + if (!rightclick && target.visible != undefined) + { + if (target.foldable) + { + if (target.visible) + fold(target); + else + unfold(target); + } + + stopPropagation(e); + e.cancel = true; + e.returnValue = false; + } + + return false; +} + +function hoverOutline(e) +{ + var target; + + if (!e) + var e = window.event; + + if (e.target) + target = e.target; + else if (e.srcElement) + target = e.srcElement; + + // work around Safari bug + if (target.nodeType == 3) + target = target.parentNode; + + while (target && target.visible == undefined) + target = target.parentNode; + + if (target && target.foldable) + target.style.cursor = "pointer"; + + return true; +} + +function unhoverOutline(e) +{ + var target; + + if (!e) + var e = window.event; + + if (e.target) + target = e.target; + else if (e.srcElement) + target = e.srcElement; + + // work around Safari bug + if (target.nodeType == 3) + target = target.parentNode; + + while (target && target.visible == undefined) + target = target.parentNode; + + if (target) + target.style.cursor = "default"; + + return true; +} + + +function stopPropagation(e) +{ + if (window.event) + { + window.event.cancelBubble = true; + //window.event.returnValue = false; + } + else if (e) + { + e.cancelBubble = true; + e.stopPropagation(); + //e.preventDefault(); + } +} + +/* can't rely on display since we set that to none to hide things */ +function isBlock(elem) +{ + var tag = elem.nodeName; + + return tag == "OL" || tag == "UL" || tag == "P" || + tag == "LI" || tag == "TABLE" || tag == "PRE" || + tag == "H1" || tag == "H2" || tag == "H3" || + tag == "H4" || tag == "H5" || tag == "H6" || + tag == "BLOCKQUOTE" || tag == "ADDRESS"; +} + +function getElementStyle(elem, IEStyleProp, CSSStyleProp) +{ + if (elem.currentStyle) + { + return elem.currentStyle[IEStyleProp]; + } + else if (window.getComputedStyle) + { + var compStyle = window.getComputedStyle(elem, ""); + return compStyle.getPropertyValue(CSSStyleProp); + } + return ""; +} + +// works with text/html and text/xhtml+xml with thanks to Simon Willison +function createElement(element) +{ + if (typeof document.createElementNS != 'undefined') + { + return document.createElementNS('http://www.w3.org/1999/xhtml', element); + } + + if (typeof document.createElement != 'undefined') + { + return document.createElement(element); + } + + return false; +} + +// designed to work with both text/html and text/xhtml+xml +function getElementsByTagName(name) +{ + if (typeof document.getElementsByTagNameNS != 'undefined') + { + return document.getElementsByTagNameNS('http://www.w3.org/1999/xhtml', name); + } + + if (typeof document.getElementsByTagName != 'undefined') + { + return document.getElementsByTagName(name); + } + + return null; +} + +/* +// clean alternative to innerHTML method, but on IE6 +// it doesn't work with named entities like +// which need to be replaced by numeric entities +function insertText(element, text) +{ + try + { + element.textContent = text; // DOM3 only + } + catch (e) + { + if (element.firstChild) + { + // remove current children + while (element.firstChild) + element.removeChild(element.firstChild); + } + + element.appendChild(document.createTextNode(text)); + } +} + +// as above, but as method of all element nodes +// doesn't work in IE6 which doesn't allow you to +// add methods to the HTMLElement prototype +if (HTMLElement != undefined) +{ + HTMLElement.prototype.insertText = function(text) { + var element = this; + + try + { + element.textContent = text; // DOM3 only + } + catch (e) + { + if (element.firstChild) + { + // remove current children + while (element.firstChild) + element.removeChild(element.firstChild); + } + + element.appendChild(document.createTextNode(text)); + } + }; +} +*/ + +function getSelectedText() +{ + try + { + if (window.getSelection) + return window.getSelection().toString(); + + if (document.getSelection) + return document.getSelection().toString(); + + if (document.selection) + return document.selection.createRange().text; + } + catch (e) + { + return ""; + } + return ""; +} +