Mercurial > hg > Papers > 2011 > prosym-shinya
changeset 10:99e1c7d2acee
add presentation
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/code/reg.ll.txt Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,121 @@ +; ModuleID = 'DFA' +global [4 x i8] c"ABC\00" ; <[4 x i8]*>:0 [#uses=4] +global [28 x i8] c"state: %s, arg: %c(int %d)\0A\00" ; <[28 x i8]*>:1 [#uses=0] + +define i32 @accept(i32 %index) { +entry: + ret i32 1 +} + +define i32 @reject(i32 %index) { +entry: + ret i32 0 +} + +define i32 @"8"(i32 %index) { +entry: + %0 = getelementptr [4 x i8]* @0, i32 0, i32 %index ; <i8*> [#uses=1] + %1 = add i32 %index, 1 ; <i32> [#uses=2] + %2 = load i8* %0 ; <i8> [#uses=1] + switch i8 %2, label %default [ + i8 0, label %case0 + ] + +default: ; preds = %entry + %3 = call i32 @reject(i32 %1) ; <i32> [#uses=1] + ret i32 %3 + +case0: ; preds = %entry + %4 = call i32 @accept(i32 %1) ; <i32> [#uses=1] + ret i32 %4 +} + +define i32 @"1_3_5_6_7"(i32 %index) { +entry: + %0 = getelementptr [4 x i8]* @0, i32 0, i32 %index ; <i8*> [#uses=1] + %1 = add i32 %index, 1 ; <i32> [#uses=4] + %2 = load i8* %0 ; <i8> [#uses=1] + switch i8 %2, label %default [ + i8 65, label %case0 + i8 67, label %case1 + i8 66, label %case2 + ] + +default: ; preds = %entry + %3 = call i32 @reject(i32 %1) ; <i32> [#uses=1] + ret i32 %3 + +case0: ; preds = %entry + %4 = call i32 @"1_2_3_5_7"(i32 %1) ; <i32> [#uses=1] + ret i32 %4 + +case1: ; preds = %entry + %5 = call i32 @"8"(i32 %1) ; <i32> [#uses=1] + ret i32 %5 + +case2: ; preds = %entry + %6 = call i32 @"1_3_4_5_7"(i32 %1) ; <i32> [#uses=1] + ret i32 %6 +} + +define i32 @"1_3_4_5_7"(i32 %index) { +entry: + %0 = getelementptr [4 x i8]* @0, i32 0, i32 %index ; <i8*> [#uses=1] + %1 = add i32 %index, 1 ; <i32> [#uses=4] + %2 = load i8* %0 ; <i8> [#uses=1] + switch i8 %2, label %default [ + i8 65, label %case0 + i8 67, label %case1 + i8 66, label %case2 + ] + +default: ; preds = %entry + %3 = call i32 @reject(i32 %1) ; <i32> [#uses=1] + ret i32 %3 + +case0: ; preds = %entry + %4 = call i32 @"1_2_3_5_7"(i32 %1) ; <i32> [#uses=1] + ret i32 %4 + +case1: ; preds = %entry + %5 = call i32 @"8"(i32 %1) ; <i32> [#uses=1] + ret i32 %5 + +case2: ; preds = %entry + %6 = call i32 @"1_3_4_5_7"(i32 %1) ; <i32> [#uses=1] + ret i32 %6 +} + +define i32 @"1_2_3_5_7"(i32 %index) { +entry: + %0 = getelementptr [4 x i8]* @0, i32 0, i32 %index ; <i8*> [#uses=1] + %1 = add i32 %index, 1 ; <i32> [#uses=4] + %2 = load i8* %0 ; <i8> [#uses=1] + switch i8 %2, label %default [ + i8 65, label %case0 + i8 67, label %case1 + i8 66, label %case2 + ] + +default: ; preds = %entry + %3 = call i32 @reject(i32 %1) ; <i32> [#uses=1] + ret i32 %3 + +case0: ; preds = %entry + %4 = call i32 @"1_2_3_5_7"(i32 %1) ; <i32> [#uses=1] + ret i32 %4 + +case1: ; preds = %entry + %5 = call i32 @"8"(i32 %1) ; <i32> [#uses=1] + ret i32 %5 + +case2: ; preds = %entry + %6 = call i32 @"1_3_4_5_7"(i32 %1) ; <i32> [#uses=1] + ret i32 %6 +} + +define i32 @unitmain(i32 %index) { +entry: + %0 = call i32 @"1_3_5_6_7"(i32 %index) ; <i32> [#uses=1] + ret i32 %0 +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/fig.graffle Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,1228 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> +<plist version="1.0"> +<dict> + <key>ActiveLayerIndex</key> + <integer>0</integer> + <key>ApplicationVersion</key> + <array> + <string>com.omnigroup.OmniGraffle</string> + <string>129.18</string> + </array> + <key>AutoAdjust</key> + <false/> + <key>CanvasColor</key> + <dict> + <key>w</key> + <string>1</string> + </dict> + <key>CanvasOrigin</key> + <string>{0, 0}</string> + <key>CanvasScale</key> + <real>1</real> + <key>ColumnAlign</key> + <integer>1</integer> + <key>ColumnSpacing</key> + <real>36</real> + <key>CreationDate</key> + <string>2010-09-07 05:31:30 +0900</string> + <key>Creator</key> + <string>ryoma</string> + <key>DisplayScale</key> + <string>1 cm = 1 cm</string> + <key>FileType</key> + <string>flat</string> + <key>GraphDocumentVersion</key> + <integer>5</integer> + <key>GraphicsList</key> + <array> + <dict> + <key>Bounds</key> + <string>{{49.75, 243}, {209.5, 46}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>HiraKakuProN-W3</string> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>68</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'95\'5d\'89\'bf\'8a\'ed (Python)\ +}</string> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>67</integer> + <key>Points</key> + <array> + <string>{410.5, 250}</string> + <string>{549.5, 250}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>HeadArrow</key> + <string>0</string> + <key>TailArrow</key> + <string>0</string> + <key>Width</key> + <real>3</real> + </dict> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>23</integer> + <key>Points</key> + <array> + <string>{-21, 212}</string> + <string>{50, 212.25}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>HeadArrow</key> + <string>0</string> + <key>TailArrow</key> + <string>0</string> + <key>Width</key> + <real>3</real> + </dict> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>65</integer> + </dict> + <key>ID</key> + <integer>66</integer> + <key>Points</key> + <array> + <string>{481.818, 190.125}</string> + <string>{483.834, 210}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>57</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Bounds</key> + <string>{{406.5, 228}, {145, 23}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>64</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'95\'5d\'83\'47\'83\'93\'83\'57\'83\'93}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{420.5, 210}, {129, 23}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>65</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 \'83\'52\'83\'93\'83\'70\'83\'43\'83\'8b\'82\'b3\'82\'ea\'82\'bd}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + </array> + <key>ID</key> + <integer>63</integer> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Bounds</key> + <string>{{433, 144.125}, {95, 26}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>56</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs34 \cf0 \expnd0\expndtw0\kerning0 +\'83\'52\'83\'93\'83\'70\'83\'43\'83\'89}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{420.5, 164.125}, {120, 26}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>57</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs34 \cf0 \expnd0\expndtw0\kerning0 +(GCC, LLVM)}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + </array> + <key>ID</key> + <integer>55</integer> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>5</integer> + </dict> + <key>ID</key> + <integer>51</integer> + <key>Points</key> + <array> + <string>{389, 165}</string> + <string>{417, 165.25}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>49</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{295, 128.5}, {90, 24}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>50</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs32 \cf0 \'90\'b6\'90\'ac\'83\'52\'81\'5b\'83\'68}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>11</integer> + </dict> + <key>ID</key> + <integer>48</integer> + <key>Points</key> + <array> + <string>{49, 203.5}</string> + <string>{92.5, 203.5}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>47</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{-21, 192}, {70, 23}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>47</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>42</integer> + </dict> + <key>ID</key> + <integer>43</integer> + <key>Points</key> + <array> + <string>{265, 244.482}</string> + <string>{294.714, 244.489}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>30</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Bounds</key> + <string>{{291, 238.5}, {97.9999, 23}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>41</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 LLVM - IR}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{295.214, 231}, {89.5697, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>42</integer> + <key>Shape</key> + <string>Rectangle</string> + </dict> + </array> + <key>ID</key> + <integer>40</integer> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>38</integer> + </dict> + <key>ID</key> + <integer>39</integer> + <key>Points</key> + <array> + <string>{265, 165.482}</string> + <string>{314.279, 165.827}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>30</integer> + <key>Info</key> + <integer>1</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Bounds</key> + <string>{{312.5, 160}, {53, 23}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>37</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 C}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{314.779, 152.5}, {48.4408, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>38</integer> + <key>Shape</key> + <string>Rectangle</string> + </dict> + </array> + <key>ID</key> + <integer>36</integer> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>30</integer> + <key>Points</key> + <array> + <string>{265, 244.482}</string> + <string>{265, 165.482}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>46</integer> + <key>Points</key> + <array> + <string>{229.5, 203.713}</string> + <string>{266, 204}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>9</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>17</integer> + </dict> + <key>ID</key> + <integer>22</integer> + <key>Points</key> + <array> + <string>{265, 203.993}</string> + <string>{314.279, 203.831}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>30</integer> + <key>Position</key> + <real>0.51251417398452759</real> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>9</integer> + </dict> + <key>ID</key> + <integer>19</integer> + <key>Points</key> + <array> + <string>{146.5, 203.5}</string> + <string>{175.5, 203.5}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>11</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Bounds</key> + <string>{{312.5, 197.75}, {53, 23}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>16</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs30 \cf0 CbC}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{314.779, 190.25}, {48.4408, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>17</integer> + <key>Shape</key> + <string>Rectangle</string> + </dict> + </array> + <key>ID</key> + <integer>15</integer> + </dict> + <dict> + <key>Bounds</key> + <string>{{93, 190}, {53, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>11</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs24 \cf0 NFA}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{176, 190}, {53, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>9</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs24 \cf0 DFA}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{101.5, 152.5}, {106, 24}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>HiraKakuProN-W3</string> + <key>Size</key> + <real>16</real> + </dict> + <key>ID</key> + <integer>7</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs32 \cf0 \'83\'52\'81\'5b\'83\'68\'90\'b6\'90\'ac\'8c\'6e}</string> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{169, 11}, {81, 39}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>6</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540 +{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural + +\f0\fs24 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{417, 142.25}, {127, 46}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>5</integer> + <key>Magnets</key> + <array> + <string>{-0.5, 0}</string> + </array> + <key>Shape</key> + <string>Rectangle</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{64, 140}, {181, 89}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3</integer> + <key>Shape</key> + <string>Rectangle</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{291, 120}, {98, 147}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>49</integer> + <key>Magnets</key> + <array> + <string>{0.5, -0.193878}</string> + </array> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>CornerRadius</key> + <real>5</real> + </dict> + </dict> + </dict> + </array> + <key>GridInfo</key> + <dict/> + <key>GuidesLocked</key> + <string>NO</string> + <key>GuidesVisible</key> + <string>YES</string> + <key>HPages</key> + <integer>1</integer> + <key>ImageCounter</key> + <integer>1</integer> + <key>IsPalette</key> + <string>NO</string> + <key>KeepToScale</key> + <false/> + <key>Layers</key> + <array> + <dict> + <key>Lock</key> + <string>NO</string> + <key>Name</key> + <string>Layer 1</string> + <key>Print</key> + <string>YES</string> + <key>View</key> + <string>YES</string> + </dict> + </array> + <key>LayoutInfo</key> + <dict/> + <key>LinksVisible</key> + <string>NO</string> + <key>MagnetsVisible</key> + <string>NO</string> + <key>MasterSheets</key> + <array> + <dict> + <key>ActiveLayerIndex</key> + <integer>0</integer> + <key>AutoAdjust</key> + <false/> + <key>CanvasColor</key> + <dict> + <key>w</key> + <string>1</string> + </dict> + <key>CanvasOrigin</key> + <string>{0, 0}</string> + <key>CanvasScale</key> + <real>1</real> + <key>ColumnAlign</key> + <integer>1</integer> + <key>ColumnSpacing</key> + <real>36</real> + <key>DisplayScale</key> + <string>1 cm = 1 cm</string> + <key>GraphicsList</key> + <array/> + <key>GridInfo</key> + <dict/> + <key>HPages</key> + <integer>1</integer> + <key>IsPalette</key> + <string>NO</string> + <key>KeepToScale</key> + <false/> + <key>Layers</key> + <array> + <dict> + <key>Lock</key> + <string>NO</string> + <key>Name</key> + <string>Layer 1</string> + <key>Print</key> + <string>YES</string> + <key>View</key> + <string>YES</string> + </dict> + </array> + <key>LayoutInfo</key> + <dict/> + <key>Orientation</key> + <integer>2</integer> + <key>RowAlign</key> + <integer>1</integer> + <key>RowSpacing</key> + <real>36</real> + <key>SheetTitle</key> + <string>Master 1</string> + <key>UniqueID</key> + <integer>1</integer> + <key>VPages</key> + <integer>1</integer> + </dict> + </array> + <key>ModificationDate</key> + <string>2010-11-19 02:40:19 +0900</string> + <key>Modifier</key> + <string>ryoma</string> + <key>NotesVisible</key> + <string>NO</string> + <key>Orientation</key> + <integer>2</integer> + <key>OriginVisible</key> + <string>NO</string> + <key>PageBreaks</key> + <string>YES</string> + <key>PrintInfo</key> + <dict> + <key>NSBottomMargin</key> + <array> + <string>coded</string> + <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFklySG</string> + </array> + <key>NSLeftMargin</key> + <array> + <string>coded</string> + <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFklySG</string> + </array> + <key>NSPaperSize</key> + <array> + <string>size</string> + <string>{595, 842}</string> + </array> + <key>NSRightMargin</key> + <array> + <string>coded</string> + <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFklySG</string> + </array> + <key>NSTopMargin</key> + <array> + <string>coded</string> + <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFklySG</string> + </array> + </dict> + <key>ReadOnly</key> + <string>NO</string> + <key>RowAlign</key> + <integer>1</integer> + <key>RowSpacing</key> + <real>36</real> + <key>SheetTitle</key> + <string>Canvas 1</string> + <key>SmartAlignmentGuidesActive</key> + <string>YES</string> + <key>SmartDistanceGuidesActive</key> + <string>NO</string> + <key>UniqueID</key> + <integer>1</integer> + <key>UseEntirePage</key> + <false/> + <key>VPages</key> + <integer>1</integer> + <key>WindowInfo</key> + <dict> + <key>CurrentSheet</key> + <integer>0</integer> + <key>DrawerTab</key> + <string>Outline</string> + <key>DrawerWidth</key> + <real>209</real> + <key>Frame</key> + <string>{{134, 39}, {1033, 707}}</string> + <key>VisibleRegion</key> + <string>{{-243, 0}, {1018, 593}}</string> + <key>Zoom</key> + <real>1</real> + </dict> +</dict> +</plist>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/index.html Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,374 @@ +<?xml version="1.0" encoding="utf-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" lang="ja" xml:lang="ja"> + <head> + <title>Implimentation of Regular Expression Engine with Dynamic Code Generation.</title> + <!-- metadata --> + <meta name="generator" content="S5" /> + <meta name="version" content="S5 1.1" /> + <meta name="presdate" content="20101014" /> + <meta name="author" content="Ryoma SHINYA" /> + <meta name="company" content="University of the Ryukyu" /> + <!-- configuration parameters --> + <meta name="defaultView" content="slideshow" /> + <meta name="controlVis" content="hidden" /> + <!-- style sheet links --> + <link rel="stylesheet" href="ui/default/slides.css" type="text/css" media="projection" id="slideProj" /> + <link rel="stylesheet" href="ui/default/outline.css" type="text/css" media="screen" id="outlineStyle" /> + <link rel="stylesheet" href="ui/default/print.css" type="text/css" media="print" id="slidePrint" /> + <link rel="stylesheet" href="ui/default/opera.css" type="text/css" media="projection" id="operaFix" /> + <!-- embedded styles --> + <style type="text/css" media="all"> + .imgcon {width: 525px; margin: 0 auto; padding: 0; text-align: center;} + #anim {width: 270px; height: 320px; position: relative; margin-top: 0.5em;} + #anim img {position: absolute; top: 42px; left: 24px;} + img#me01 {top: 0; left: 0;} + img#me02 {left: 23px;} + img#me04 {top: 44px;} + img#me05 {top: 43px;left: 36px;} + #tbcom td, #tbcom th, #tbcom {border: 1px solid black; padding: 2px;} + </style> + <!-- S5 JS --> + <script src="ui/default/slides.js" type="text/javascript"></script> + </head> + <body> + <div class="layout"> + <div id="controls"><!-- DO NOT EDIT --></div> + <div id="currentSlide"><!-- DO NOT EDIT --></div> + <div id="header"></div> + <div id="footer"> + <h1>Implimentation of Regular Expression Engine with Dynamic Code Generation.</h1> + <h2>ソフトウェア科学会; 2010/10/14</h2> + </div> + </div> + <div class="presentation"> + <div class="slide"> + <h1>動的なコード生成を用いた<br/>正規表現評価器の実装</h1> + <h3>新屋 良磨, 河野 真治</h3> + <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4> + <div class="handout"></div> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>研究目的と背景 (1)</h1> + <ul> + <li>正規表現は, パターンマッチによるテキストの検索等に利用されている.</li> + <li>シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい. </li><br/> + <li class="incremental">プログラムの開発は, 生産性の高い言語によって行われることが開発者にとって望ましい.</li> + <li class="incremental">開発効率 or 実行効率 ?</li><span class="incremental"></span> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>研究目的と背景 (2)</h1> + <ul> + <li>生産性の高い言語によって実装したプログラム(生成系)から, 抽象度が低く性能の高い言語のコード生成を行うプログラミング手法がある.</li> + <li>この手法では, <blue>性能を保ったまま開発効率に優れるという</blue>利点がある.</li><br/> + <li class="incremental">そこで本研究では, 与えられた正規表現を認識するコード(C言語等の)を生成する正規表現評価器の実装を行った.</li><span class="incremental"></span> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>正規表現とは</h1> + <ul> + <li>テキストのパターンマッチング記法.</li> + <p>ex: "<blue>(A|B)*C</blue>" -> "A"または"B", の0回以上の繰り返し直後に"C"<span class="incremental">: "C","ABC","ABBBBC"</span></p> + <li>GNU grep などのテキスト検索ツール等で利用されている.</li> + <br/><br/> + <li class="incremental">正規表現は(NFAを経て)等価なDFA(決定性有限オートマトン)に変換可能.</li> + <li class="incremental">主張: DFAは直接コードで表現できる.</li><span class="incremental"></span> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>本実装の特徴</h1> + <ul> + <li>DFAの状態遷移に対応した, <strong>関数遷移</strong>を行うコードを生成.</li> + <img src="pix/flow.png" style="height: 7em;"/> + <li>生成系は<strong>Python</strong>で実装.</li> + <li>正規表現の<strong>連接</strong>, <strong>集合和</strong>, <strong>閉包</strong> の基本演算に対応.<br/> + <span class="incremental">"<blue>(A|B)*C</blue>" -> [[[AとBの集合和]の閉包]とCの連接]</span></li> + <li>マルチバイト文字: <strong>UTF-8</strong> に対応(内部コード).</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>正規表現からDFAへの変換</h1> + <ul> + <li>正規表現を等価な<red>NFA</red>に変換.</li> + <li>NFAを部分集合構成法を用いて<red>DFA</red>に変換.</li> + <p>図: 正規表現"<blue>(A|B)*C</blue>"と等価なDFA</p> + <img src="pix/dfa.png" style="height: 7em;"/> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>DFA変換のコスト</h1> + <ul> + <li>DFAへの変換コストを, 正規表現中の単語数で計測.<br/><br/> + <span class="incremental">図: N個の単語の集合和からDFAへの変換時間.</span></li> + <img src="pix/bench_translation.png" style="height: 12em;"/> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>DFAからのコード生成</h1> + <ul> + <li>DFAによる状態遷移を<strong>関数遷移</strong>で行うコードを生成.</li> + <li><blue>C</blue>, <blue>CbC</blue>, <blue>LLVM-IR</blue> それぞれのコードを生成する生成系を実装した.</li> + <img src="pix/flow.png" style="height: 7em;"/> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>コード生成: <a href="code/reg.c.txt" target="blank"><red>C</red></a></h1> + <ul> + <li>DFAによる状態遷移を, 関数遷移として表現.</li> + <li>入力文字列による分岐は<strong>switch文</strong>, 状態遷移は<strong>関数遷移</strong>.<br/> + <pre style="font-size: 0.6em;"> +/* "<blue>(A|B)*C</blue>"に対応するCコード. /* +int state_1(unsigned char* s) { + switch(*s++) { + case 0: /* match */ + return accept(s); + default: return reject(s); + } +} + +int state_0(unsigned char* s) { + switch(*s++) { + case 65: /* match A */ + return state_0(s); + case 66: /* match B */ + return state_0(s); + case 67: /* match C */ + return state_1(s); + default: return reject(s); + } +} + </pre> + </li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>コード生成: <a href="code/reg.cbc.txt" target="blank"><red>CbC</red> (1)</a></h1> + <ul> + <li>CbC(Continuation based C)は</li> + <ul> + <li>関数よりも小さなプログラミング単位として<strong>コードセグメント</strong>を持つ.</li> + <li>コードセグメントによる<strong>継続</strong>を基本としたCの下位言語である.</li> + <li>CbCコンパイラがGCCを拡張する形で実装されている.</li> + </ul> + <li class="incremental">DFAの遷移は継続的な処理であり, CbCではそれを明示的に記述できる.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>コード生成: <a href="code/reg.cbc.txt" target="blank"><red>CbC</red></a> (2)</h1> + <ul> + <li>CbCでも, 前節で紹介したCと同様に生成を行ったが, 関数ではなくコードセグメントを用いている.</li> + <pre style="font-size: 0.6em;"> + +/* "<blue>(A|B)*C</blue>"に対応するCコード. /* +__code state_1(unsigned char *s) { + switch(*s++) { + case 0: /* match */ + goto accept(s); + default: goto reject(s); + } +} + +__code state_0(unsigned char *s) { + switch(*s++) { + case 65: /* match A */ + goto state_0(s); + case 66: /* match B */ + goto state_0(s); + case 67: /* match C */ + goto state_1(s); + default: goto reject(s); + } +} + </pre> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>コード生成: <a href="code/reg.ll.txt" target="blank"><red>LLVM-IR</red></a></h1> + <ul> + <li>LLVM(Low Level Virtual Machine)は</li> + <ul> + <li>構文解析やコード生成など, 機能単位で再利用可能なコンパイラ基盤.</li> + <li>様々な最適化が実装されている.</li> + <li>LLVM内部表現であるLLVM-IRを, 直接操作するAPIが提供されている.</li> + </ul> + <li>Cと同様な処理を行うコードを, LLVM-IRを直接操作して生成.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>生成系の比較 (1)</h1> + <ul> + <li>コンパイル速度<br/> + 表: N個の単語の集合和から生成されたコードのコンパイル時間 (<blue>最適化有り(O3)</blue>).</li> + <table id="tbcom"> + <tr><th>N (単語数)</th><td>1</td><td>10</td><td>100</td></td> + <tr><th><strong>C (GCC)</strong></th><td>0.34s</td><td>0.78s</td><td>4.27s</td></td> + <tr><th><strong>CbC (GCC)</strong></th><td>0.75s</td><td>1.03s</td><td>9.43s</td></td> + <tr><th><strong>LLVM-IR (LLVM)</strong></th><td>0.044s</td><td>0.08s</td><td>0.47s</td></td> + </table> + <li>LLVMによるコンパイルが, GCCによるコンパイルに比べ10倍程高速な結果がでた.</li> + <li class="incremental">主張: コンパイル速度はあまり重要でない.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>生成系の比較 (2)</h1> + <ul> + <li>コンパイルされたプログラムの実行速度</li> + <ul> + <li>C/CbC/LLVM-IRをコンパイルしたプログラムの実行速度に, あまり差がでなかった.</li> + <li>3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.</li> + </ul> + <li class="incremental">生成されたコードは, 関数呼び出しとswitch文によるシンプルなプログラムなので, 最適化によって性能の等しいネイティブコードが生成されたためと思われる.</li> + <li class="incremental">CbCでは, 関数呼び出しより軽量な状態遷移である継続を用いて実装しているため, コンパイラの最適化に依らず性能の高いコードが保証されている -> 生成コードとして最適.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>性能評価: vs GNU grep.</h1> + <ul> + <li>本実装により生成したCコードとGNU grep 2.6.3/2.5.4 の検索時間を計測(変換/コンパイル時間も含む).</li> + <li>生成コード, GNU grep は共にGCC 4.4.1(-O3) でコンパイル.</li> + <li>検索テキスト: Wikipedia 日本語版全記事 (UTF-8, 8000万行) </li> + <li> + 3つのパターンによるベンチマーク.<br/> + <table> + <tr><th><blue>fixed-string</blue></th><td>: 固定文字列</td></tr> + <tr><th><blue>simple-regex</blue></th><td>: 単純な正規表現</td></tr> + <tr><th><blue>complex-regex</blue></th><td>: 複雑な正規表現</td></tr> + </table> + <p class="incremental">"複雑さ" = 変換されたDFAの状態数/遷移規則の多さ.</p> + </li> + <!-- + <li>実験環境.</li><br/> + <table style="border: solid black 1px;"> + <tr> + <th style="border: solid black 1px;">CPU</th> + <td style="border: solid black 1px;">Intel Core i7 950 @3.0GHz</td> + </tr> + <tr style="border: solid black 1px;"> + <th style="border: solid black 1px;">Memory</th> + <td style="border: solid black 1px;">16GB</td> + </tr> + <tr style="border: solid black 1px;"> + <th style="border: solid black 1px;">Compiler</th> + <td style="border: solid black 1px;">GCC 4.4.1</td> + </tr> + <tr style="border: solid black 1px;"> + <th style="border: solid black 1px;">Text</th> + <td style="border: solid black 1px;">Wikipedia 日本語版全記事<br/>XML, UTF-8, 4.7GB (8000万行)</td> + </tr> + </table> + --> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>テストケース</h1> + <ul> + <li> + <strong>fixed-string</strong> - 固定文字列でのマッチング<br/> + パターン : "<blue>Wikipedia</blue>" - <a href="pix/fixed-string.png" target="blank">図</a><br/> + マッチ行数: 348936行 + </li> + <li> + <strong>simple-regex</strong> - 単純な正規表現でのマッチング<br/> + <span class="incremental">Wikipediaの記事のカテゴリタグ記述にマッチ</span><br/> + パターン : "<blue>^\*+ \[\[</blue>" - <a href="pix/simple-regex.png" target="blank">図</a><br/> + マッチ行数: 1503行 + </li> + <li> + <strong>complex-regex</strong> - 複雑な正規表現でのマッチング<br/> + パターン : "<blue style='font-size: 70%;'>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>" - <a href="pix/complex-regex.png" target="blank">図</a><br/> + マッチ行数: 3439028行 + </li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>性能評価: 結果</h1> + <img src="pix/bench_grep.png" style="height: 11em;"/> + <ul> + <li class="incremental">fixed-stringでは, 固定文字列フィルタの差が大きい.</li> + <li class="incremental">complex-regexでは, 本実装がGNU grepより高速な結果を出した. *Repeat: コード生成, コンパイル時間も含む.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>まとめ</h1> + <ul> + <li>生成系を開発効率に優れた言語であるPythonで実装することで, 少ない記述量で正規表現評価器を実装した.</li> + <table> + <tr><th><blue>本実装 (Python)</blue></th><td>: 1500行 (C生成系: テストコード含む)</td></tr> + <tr><th><blue>GNU grep (C)</blue></th><td>: 15000行 (コアのみ)</td></tr> + </table> + <li>最終的に得られた正規表現評価器の性能は, GNU grep に勝るテストケースもあり, 性能も良い.</li> + <li class="incremental">目的: シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>今後の課題</h1> + <ul> + <li>正規表現評価器の機能強化</li> + <ul> + <li>固定文字列フィルタリング(Boyer-Moore等)や後方参照の実装等.</li> + <li>後方参照: "(A*)B\1" -> "\1"は(A*)でマッチした文字列.</li> + <li class="incremental">本実装は関数遷移によるマッチングを行うので, バックトラック処理を容易に記述できる.</li> + </ul> + <li>コード生成の最適化, 生成手法の評価.</li> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>展望</h1> + <ul> + <li>grep 以外のソフトウェアへの応用</li> + <ul> + <li>正規表現に対して, 検索対象の規模が大きいプログラムと相性が良い.</li> + <li>一度コンパイルすればマッチングを行うネイティブコードが得られる.</li> + <li>同様のパターンで何度もマッチングを行うプログラムと相性が良い.</li> + <li class="incremental">スパムフィルタの単語検索など.</li> + </ul> + <strong class="incremental">ご清聴ありがとうございました.</strong> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>付録: UTF-8</h1> + <ul> + <li>Unicodeの符号化形式 -> マルチバイト文字に対応.</li> + <li>符号単位は8bit.</li> + <li>ASCIIとの互換性を持っている.</li> + <li>プログラムでのバイト操作が非常に容易な, 素晴らしい符号化形式.</li> + <ul> + <li>文字の先頭1ByteでByteが分かる</li> + <li>先頭Byteと中間Byteは先頭2bitで判別可能.</li> + </ul> + </ul> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>正規表現: UTF-8</h1> + <ul> + <li>入力の最小単位として, Unicode文字単位でNFA,DFAを構築すれば良い.</li> + <img src="pix/utf-dfa.png" stye="height: 11em;"/> + <li class="incremental">GNU grep 2.5.X では, DFAの遷移毎に入力文字に対して mbrtowc() を用いてwchar型への変換を行っている -> ボトルネック (90%以上)</li> + </ul> + </div> + </div> + </body> +</html>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/src/regllvm_abstract.txt Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,9 @@ +新屋良磨 + +Subject +LLVMを用いた正規表現コンパイラの実装と検証 +Implementation and Evaluation of Regular Expression Compiler using LLVM + +内容 +正規表現は等価なオートマトンに変換できる. 当研究室では Continuation based C という状態遷移記述に適したCの下位言語を提案している. +本研究では, 文字列として与えられた正規表現から,CbCで記述された状態遷移ベースの正規表現マッチャの生成, 及びコンパイラ基盤LLVMを利用したJITコンパイルによるマッチャの実行バイナリを生成するコンパイラを実装し、マッチングにおけるベンチマークを行い性能を評価する。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/framing.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,23 @@ +/* The following styles size, place, and layer the slide components. + Edit these if you want to change the overall slide layout. + The commented lines can be uncommented (and modified, if necessary) + to help you with the rearrangement process. */ + +/* target = 1024x768 */ + +div#header, div#footer, .slide {width: 100%; top: 0; left: 0;} +div#header {top: 0; height: 3em; z-index: 1;} +div#footer {top: auto; bottom: 0; height: 2.5em; z-index: 5;} +.slide {top: 0; width: 92%; padding: 3.5em 4% 4%; z-index: 2; list-style: none;} +div#controls {left: 50%; bottom: 0; width: 50%; z-index: 100;} +div#controls form {position: absolute; bottom: 0; right: 0; width: 100%; + margin: 0;} +#currentSlide {position: absolute; width: 10%; left: 45%; bottom: 1em; z-index: 10;} +html>body #currentSlide {position: fixed;} + +/* +div#header {background: #FCC;} +div#footer {background: #CCF;} +div#controls {background: #BBD;} +div#currentSlide {background: #FFC;} +*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/iepngfix.htc Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,42 @@ +<public:component> +<public:attach event="onpropertychange" onevent="doFix()" /> + +<script> + +// IE5.5+ PNG Alpha Fix v1.0 by Angus Turnbull http://www.twinhelix.com +// Free usage permitted as long as this notice remains intact. + +// This must be a path to a blank image. That's all the configuration you need here. +var blankImg = 'ui/default/blank.gif'; + +var f = 'DXImageTransform.Microsoft.AlphaImageLoader'; + +function filt(s, m) { + if (filters[f]) { + filters[f].enabled = s ? true : false; + if (s) with (filters[f]) { src = s; sizingMethod = m } + } else if (s) style.filter = 'progid:'+f+'(src="'+s+'",sizingMethod="'+m+'")'; +} + +function doFix() { + if ((parseFloat(navigator.userAgent.match(/MSIE (\S+)/)[1]) < 5.5) || + (event && !/(background|src)/.test(event.propertyName))) return; + + if (tagName == 'IMG') { + if ((/\.png$/i).test(src)) { + filt(src, 'image'); // was 'scale' + src = blankImg; + } else if (src.indexOf(blankImg) < 0) filt(); + } else if (style.backgroundImage) { + if (style.backgroundImage.match(/^url[("']+(.*\.png)[)"']+$/i)) { + var s = RegExp.$1; + style.backgroundImage = ''; + filt(s, 'crop'); + } else filt(); + } +} + +doFix(); + +</script> +</public:component> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/opera.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,7 @@ +/* DO NOT CHANGE THESE unless you really want to break Opera Show */ +.slide { + visibility: visible !important; + position: static !important; + page-break-before: always; +} +#slide0 {page-break-before: avoid;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/outline.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,15 @@ +/* don't change this unless you want the layout stuff to show up in the outline view! */ + +.layout div, #footer *, #controlForm * {display: none;} +#footer, #controls, #controlForm, #navLinks, #toggle { + display: block; visibility: visible; margin: 0; padding: 0;} +#toggle {float: right; padding: 0.5em;} +html>body #toggle {position: fixed; top: 0; right: 0;} + +/* making the outline look pretty-ish */ + +#slide0 h1, #slide0 h2, #slide0 h3, #slide0 h4 {border: none; margin: 0;} +#slide0 h1 {padding-top: 1.5em;} +.slide h1 {margin: 1.5em 0 0; padding-top: 0.25em; + border-top: 1px solid #888; border-bottom: 1px solid #AAA;} +#toggle {border: 1px solid; border-width: 0 0 1px 1px; background: #FFF;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/pretty.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,89 @@ +/* Following are the presentation styles -- edit away! */ + +body {background: #FFF url(bodybg.gif) -16px 0 no-repeat; color: #000; font-size: 2em;} +:link, :visited {text-decoration: none; color: #00C;} +#controls :active {color: #88A !important;} +#controls :focus {outline: 1px dotted #227;} +h1, h2, h3, h4 {font-size: 100%; margin: 0; padding: 0; font-weight: inherit;} +ul, pre {margin: 0; line-height: 1em;} +html, body {margin: 0; padding: 0;} + +blockquote, q {font-style: italic;} +blockquote {padding: 0 2em 0.5em; margin: 0 1.5em 0.5em; text-align: center; font-size: 1em;} +blockquote p {margin: 0;} +blockquote i {font-style: normal;} +blockquote b {display: block; margin-top: 0.5em; font-weight: normal; font-size: smaller; font-style: normal;} +blockquote b i {font-style: italic;} + +kbd {font-weight: bold; font-size: 1em;} +sup {font-size: smaller; line-height: 1px;} + +.slide code {padding: 2px 0.25em; font-weight: bold; color: #533;} +.slide code.bad, code del {color: red;} +.slide red {color: red;} +.slide black {color: black;} +.slide blue {color: blue;} +.slide code.old {color: silver;} +.slide pre {padding: 0; margin: 0.25em 0 0.5em 0.5em; color: #533; font-size: 90%;} +.slide pre code {display: block;} +.slide ul {margin-left: 5%; margin-right: 7%; list-style: disc;} +.slide li {margin-top: 0.75em; margin-right: 0;} +.slide ul ul {line-height: 1;} +.slide ul ul li {margin: .2em; font-size: 85%; list-style: square;} +.slide img.leader {display: block; margin: 0 auto;} + +div#header, div#footer {background: #005; color: #AAB; + font-family: Verdana, Helvetica, sans-serif;} +div#header {background: #005 url(bodybg.gif) -16px 0 no-repeat; + line-height: 1px;} +div#footer {font-size: 0.5em; font-weight: bold; padding: 1em 0;} +#footer h1, #footer h2 {display: block; padding: 0 1em;} +#footer h2 {font-style: italic;} + +div.long {font-size: 0.75em;} +.slide h1 {position: absolute; top: 0.7em; left: 87px; z-index: 1; + margin: 0; padding: 0.3em 0 0 50px; white-space: nowrap; + font: bold 150%/1em Helvetica, sans-serif; text-transform: capitalize; + color: #DDE; background: #005;} +.slide h3 {font-size: 130%;} +h1 abbr {font-variant: small-caps;} + +div#controls {position: absolute; left: 50%; bottom: 0; + width: 50%; + text-align: right; font: bold 0.9em Verdana, Helvetica, sans-serif;} +html>body div#controls {position: fixed; padding: 0 0 1em 0; + top: auto;} +div#controls form {position: absolute; bottom: 0; right: 0; width: 100%; + margin: 0; padding: 0;} +#controls #navLinks a {padding: 0; margin: 0 0.5em; + background: #005; border: none; color: #779; + cursor: pointer;} +#controls #navList {height: 1em;} +#controls #navList #jumplist {position: absolute; bottom: 0; right: 0; background: #DDD; color: #227;} + +#currentSlide {text-align: center; font-size: 0.5em; color: #449;} + +#slide0 {padding-top: 3.5em; font-size: 90%;} +#slide0 h1 {position: static; margin: 1em 0 0; padding: 0; + font: bold 2em Helvetica, sans-serif; white-space: normal; + color: #000; background: transparent;} +#slide0 h2 {font: bold italic 1em Helvetica, sans-serif; margin: 0.25em;} +#slide0 h3 {margin-top: 1.5em; font-size: 1.5em;} +#slide0 h4 {margin-top: 0; font-size: 1em;} + +ul.urls {list-style: none; display: inline; margin: 0;} +.urls li {display: inline; margin: 0;} +.note {display: none;} +.external {border-bottom: 1px dotted gray;} +html>body .external {border-bottom: none;} +.external:after {content: " \274F"; font-size: smaller; color: #77B;} + +.incremental, .incremental *, .incremental *:after {color: #DDE; visibility: visible;} +img.incremental {visibility: hidden;} +.slide .current {color: #B02;} + + +/* diagnostics + +li:after {content: " [" attr(class) "]"; color: #F88;} + */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/print.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,1 @@ +/* The following rule is necessary to have all slides appear in print! DO NOT REMOVE IT! */ .slide, ul {page-break-inside: avoid; visibility: visible !important;} h1 {page-break-after: avoid;} body {font-size: 12pt; background: white;} * {color: black;} #slide0 h1 {font-size: 200%; border: none; margin: 0.5em 0 0.25em;} #slide0 h3 {margin: 0; padding: 0;} #slide0 h4 {margin: 0 0 0.5em; padding: 0;} #slide0 {margin-bottom: 3em;} h1 {border-top: 2pt solid gray; border-bottom: 1px dotted silver;} .extra {background: transparent !important;} div.extra, pre.extra, .example {font-size: 10pt; color: #333;} ul.extra a {font-weight: bold;} p.example {display: none;} #header {display: none;} #footer h1 {margin: 0; border-bottom: 1px solid; color: gray; font-style: italic;} #footer h2, #controls {display: none;} /* The following rule keeps the layout stuff out of print. Remove at your own risk! */ .layout, .layout * {display: none !important;} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/s5-core.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,9 @@ +/* Do not edit or override these styles! The system will likely break if you do. */ + +div#header, div#footer, div#controls, .slide {position: absolute;} +html>body div#header, html>body div#footer, + html>body div#controls, html>body .slide {position: fixed;} +.handout {display: none;} +.layout {display: block;} +.slide, .hideme, .incremental {visibility: hidden;} +#slide0 {visibility: visible;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/slides.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,3 @@ +@import url(s5-core.css); /* required to make the slide show run at all */ +@import url(framing.css); /* sets basic placement and size of slide components */ +@import url(pretty.css); /* stuff that makes the slides look better than blah */ \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/default/slides.js Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,552 @@ +// S5 v1.1 slides.js -- released into the Public Domain +// +// Please see http://www.meyerweb.com/eric/tools/s5/credits.html for information +// about all the wonderful and talented contributors to this code! + +var undef; +var slideCSS = ''; +var snum = 0; +var smax = 1; +var incpos = 0; +var number = undef; +var s5mode = true; +var defaultView = 'slideshow'; +var controlVis = 'visible'; + +var isIE = navigator.appName == 'Microsoft Internet Explorer' ? 1 : 0; +var isOp = navigator.userAgent.indexOf('Opera') > -1 ? 1 : 0; +var isGe = navigator.userAgent.indexOf('Gecko') > -1 && navigator.userAgent.indexOf('Safari') < 1 ? 1 : 0; + +function hasClass(object, className) { + if (!object.className) return false; + return (object.className.search('(^|\\s)' + className + '(\\s|$)') != -1); +} + +function hasValue(object, value) { + if (!object) return false; + return (object.search('(^|\\s)' + value + '(\\s|$)') != -1); +} + +function removeClass(object,className) { + if (!object) return; + object.className = object.className.replace(new RegExp('(^|\\s)'+className+'(\\s|$)'), RegExp.$1+RegExp.$2); +} + +function addClass(object,className) { + if (!object || hasClass(object, className)) return; + if (object.className) { + object.className += ' '+className; + } else { + object.className = className; + } +} + +function GetElementsWithClassName(elementName,className) { + var allElements = document.getElementsByTagName(elementName); + var elemColl = new Array(); + for (var i = 0; i< allElements.length; i++) { + if (hasClass(allElements[i], className)) { + elemColl[elemColl.length] = allElements[i]; + } + } + return elemColl; +} + +function isParentOrSelf(element, id) { + if (element == null || element.nodeName=='BODY') return false; + else if (element.id == id) return true; + else return isParentOrSelf(element.parentNode, id); +} + +function nodeValue(node) { + var result = ""; + if (node.nodeType == 1) { + var children = node.childNodes; + for (var i = 0; i < children.length; ++i) { + result += nodeValue(children[i]); + } + } + else if (node.nodeType == 3) { + result = node.nodeValue; + } + return(result); +} + +function slideLabel() { + var slideColl = GetElementsWithClassName('*','slide'); + var list = document.getElementById('jumplist'); + smax = slideColl.length; + for (var n = 0; n < smax; n++) { + var obj = slideColl[n]; + + var did = 'slide' + n.toString(); + obj.setAttribute('id',did); + if (isOp) continue; + + var otext = ''; + var menu = obj.firstChild; + if (!menu) continue; // to cope with empty slides + while (menu && menu.nodeType == 3) { + menu = menu.nextSibling; + } + if (!menu) continue; // to cope with slides with only text nodes + + var menunodes = menu.childNodes; + for (var o = 0; o < menunodes.length; o++) { + otext += nodeValue(menunodes[o]); + } + list.options[list.length] = new Option(n + ' : ' + otext, n); + } +} + +function currentSlide() { + var cs; + if (document.getElementById) { + cs = document.getElementById('currentSlide'); + } else { + cs = document.currentSlide; + } + cs.innerHTML = '<span id="csHere">' + snum + '<\/span> ' + + '<span id="csSep">\/<\/span> ' + + '<span id="csTotal">' + (smax-1) + '<\/span>'; + if (snum == 0) { + cs.style.visibility = 'hidden'; + } else { + cs.style.visibility = 'visible'; + } +} + +function go(step) { + if (document.getElementById('slideProj').disabled || step == 0) return; + var jl = document.getElementById('jumplist'); + var cid = 'slide' + snum; + var ce = document.getElementById(cid); + if (incrementals[snum].length > 0) { + for (var i = 0; i < incrementals[snum].length; i++) { + removeClass(incrementals[snum][i], 'current'); + removeClass(incrementals[snum][i], 'incremental'); + } + } + if (step != 'j') { + snum += step; + lmax = smax - 1; + if (snum > lmax) snum = lmax; + if (snum < 0) snum = 0; + } else + snum = parseInt(jl.value); + var nid = 'slide' + snum; + var ne = document.getElementById(nid); + if (!ne) { + ne = document.getElementById('slide0'); + snum = 0; + } + if (step < 0) {incpos = incrementals[snum].length} else {incpos = 0;} + if (incrementals[snum].length > 0 && incpos == 0) { + for (var i = 0; i < incrementals[snum].length; i++) { + if (hasClass(incrementals[snum][i], 'current')) + incpos = i + 1; + else + addClass(incrementals[snum][i], 'incremental'); + } + } + if (incrementals[snum].length > 0 && incpos > 0) + addClass(incrementals[snum][incpos - 1], 'current'); + ce.style.visibility = 'hidden'; + ne.style.visibility = 'visible'; + jl.selectedIndex = snum; + currentSlide(); + number = 0; +} + +function goTo(target) { + if (target >= smax || target == snum) return; + go(target - snum); +} + +function subgo(step) { + if (step > 0) { + removeClass(incrementals[snum][incpos - 1],'current'); + removeClass(incrementals[snum][incpos], 'incremental'); + addClass(incrementals[snum][incpos],'current'); + incpos++; + } else { + incpos--; + removeClass(incrementals[snum][incpos],'current'); + addClass(incrementals[snum][incpos], 'incremental'); + addClass(incrementals[snum][incpos - 1],'current'); + } +} + +function toggle() { + var slideColl = GetElementsWithClassName('*','slide'); + var slides = document.getElementById('slideProj'); + var outline = document.getElementById('outlineStyle'); + if (!slides.disabled) { + slides.disabled = true; + outline.disabled = false; + s5mode = false; + fontSize('1em'); + for (var n = 0; n < smax; n++) { + var slide = slideColl[n]; + slide.style.visibility = 'visible'; + } + } else { + slides.disabled = false; + outline.disabled = true; + s5mode = true; + fontScale(); + for (var n = 0; n < smax; n++) { + var slide = slideColl[n]; + slide.style.visibility = 'hidden'; + } + slideColl[snum].style.visibility = 'visible'; + } +} + +function showHide(action) { + var obj = GetElementsWithClassName('*','hideme')[0]; + switch (action) { + case 's': obj.style.visibility = 'visible'; break; + case 'h': obj.style.visibility = 'hidden'; break; + case 'k': + if (obj.style.visibility != 'visible') { + obj.style.visibility = 'visible'; + } else { + obj.style.visibility = 'hidden'; + } + break; + } +} + +// 'keys' code adapted from MozPoint (http://mozpoint.mozdev.org/) +function keys(key) { + if (!key) { + key = event; + key.which = key.keyCode; + } + if (key.which == 84) { + toggle(); + return; + } + if (s5mode) { + switch (key.which) { + case 10: // return + case 13: // enter + if (window.event && isParentOrSelf(window.event.srcElement, 'controls')) return; + if (key.target && isParentOrSelf(key.target, 'controls')) return; + if(number != undef) { + goTo(number); + break; + } + case 32: // spacebar + case 34: // page down + case 39: // rightkey + case 40: // downkey + if(number != undef) { + go(number); + } else if (!incrementals[snum] || incpos >= incrementals[snum].length) { + go(1); + } else { + subgo(1); + } + break; + case 33: // page up + case 37: // leftkey + case 38: // upkey + if(number != undef) { + go(-1 * number); + } else if (!incrementals[snum] || incpos <= 0) { + go(-1); + } else { + subgo(-1); + } + break; + case 36: // home + goTo(0); + break; + case 35: // end + goTo(smax-1); + break; + case 67: // c + showHide('k'); + break; + } + if (key.which < 48 || key.which > 57) { + number = undef; + } else { + if (window.event && isParentOrSelf(window.event.srcElement, 'controls')) return; + if (key.target && isParentOrSelf(key.target, 'controls')) return; + number = (((number != undef) ? number : 0) * 10) + (key.which - 48); + } + } + return false; +} + +function clicker(e) { + number = undef; + var target; + if (window.event) { + target = window.event.srcElement; + e = window.event; + } else target = e.target; + if (target.getAttribute('href') != null || hasValue(target.rel, 'external') || isParentOrSelf(target, 'controls') || isParentOrSelf(target,'embed') || isParentOrSelf(target,'object')) return true; + if (!e.which || e.which == 1) { + if (!incrementals[snum] || incpos >= incrementals[snum].length) { + go(1); + } else { + subgo(1); + } + } +} + +function findSlide(hash) { + var target = null; + var slides = GetElementsWithClassName('*','slide'); + for (var i = 0; i < slides.length; i++) { + var targetSlide = slides[i]; + if ( (targetSlide.name && targetSlide.name == hash) + || (targetSlide.id && targetSlide.id == hash) ) { + target = targetSlide; + break; + } + } + while(target != null && target.nodeName != 'BODY') { + if (hasClass(target, 'slide')) { + return parseInt(target.id.slice(5)); + } + target = target.parentNode; + } + return null; +} + +function slideJump() { + if (window.location.hash == null) return; + var sregex = /^#slide(\d+)$/; + var matches = sregex.exec(window.location.hash); + var dest = null; + if (matches != null) { + dest = parseInt(matches[1]); + } else { + dest = findSlide(window.location.hash.slice(1)); + } + if (dest != null) + go(dest - snum); +} + +function fixLinks() { + var thisUri = window.location.href; + thisUri = thisUri.slice(0, thisUri.length - window.location.hash.length); + var aelements = document.getElementsByTagName('A'); + for (var i = 0; i < aelements.length; i++) { + var a = aelements[i].href; + var slideID = a.match('\#slide[0-9]{1,2}'); + if ((slideID) && (slideID[0].slice(0,1) == '#')) { + var dest = findSlide(slideID[0].slice(1)); + if (dest != null) { + if (aelements[i].addEventListener) { + aelements[i].addEventListener("click", new Function("e", + "if (document.getElementById('slideProj').disabled) return;" + + "go("+dest+" - snum); " + + "if (e.preventDefault) e.preventDefault();"), true); + } else if (aelements[i].attachEvent) { + aelements[i].attachEvent("onclick", new Function("", + "if (document.getElementById('slideProj').disabled) return;" + + "go("+dest+" - snum); " + + "event.returnValue = false;")); + } + } + } + } +} + +function externalLinks() { + if (!document.getElementsByTagName) return; + var anchors = document.getElementsByTagName('a'); + for (var i=0; i<anchors.length; i++) { + var anchor = anchors[i]; + if (anchor.getAttribute('href') && hasValue(anchor.rel, 'external')) { + anchor.target = '_blank'; + addClass(anchor,'external'); + } + } +} + +function createControls() { + var controlsDiv = document.getElementById("controls"); + if (!controlsDiv) return; + var hider = ' onmouseover="showHide(\'s\');" onmouseout="showHide(\'h\');"'; + var hideDiv, hideList = ''; + if (controlVis == 'hidden') { + hideDiv = hider; + } else { + hideList = hider; + } + controlsDiv.innerHTML = '<form action="#" id="controlForm"' + hideDiv + '>' + + '<div id="navLinks">' + + '<a accesskey="t" id="toggle" href="javascript:toggle();">Ø<\/a>' + + '<a accesskey="z" id="prev" href="javascript:go(-1);">«<\/a>' + + '<a accesskey="x" id="next" href="javascript:go(1);">»<\/a>' + + '<div id="navList"' + hideList + '><select id="jumplist" onchange="go(\'j\');"><\/select><\/div>' + + '<\/div><\/form>'; + if (controlVis == 'hidden') { + var hidden = document.getElementById('navLinks'); + } else { + var hidden = document.getElementById('jumplist'); + } + addClass(hidden,'hideme'); +} + +function fontScale() { // causes layout problems in FireFox that get fixed if browser's Reload is used; same may be true of other Gecko-based browsers + if (!s5mode) return false; + var vScale = 22; // both yield 32 (after rounding) at 1024x768 + var hScale = 32; // perhaps should auto-calculate based on theme's declared value? + if (window.innerHeight) { + var vSize = window.innerHeight; + var hSize = window.innerWidth; + } else if (document.documentElement.clientHeight) { + var vSize = document.documentElement.clientHeight; + var hSize = document.documentElement.clientWidth; + } else if (document.body.clientHeight) { + var vSize = document.body.clientHeight; + var hSize = document.body.clientWidth; + } else { + var vSize = 700; // assuming 1024x768, minus chrome and such + var hSize = 1024; // these do not account for kiosk mode or Opera Show + } + var newSize = Math.min(Math.round(vSize/vScale),Math.round(hSize/hScale)); + fontSize(newSize + 'px'); + if (isGe) { // hack to counter incremental reflow bugs + var obj = document.getElementsByTagName('body')[0]; + obj.style.display = 'none'; + obj.style.display = 'block'; + } +} + +function fontSize(value) { + if (!(s5ss = document.getElementById('s5ss'))) { + if (!isIE) { + document.getElementsByTagName('head')[0].appendChild(s5ss = document.createElement('style')); + s5ss.setAttribute('media','screen, projection'); + s5ss.setAttribute('id','s5ss'); + } else { + document.createStyleSheet(); + document.s5ss = document.styleSheets[document.styleSheets.length - 1]; + } + } + if (!isIE) { + while (s5ss.lastChild) s5ss.removeChild(s5ss.lastChild); + s5ss.appendChild(document.createTextNode('body {font-size: ' + value + ' !important;}')); + } else { + document.s5ss.addRule('body','font-size: ' + value + ' !important;'); + } +} + +function notOperaFix() { + slideCSS = document.getElementById('slideProj').href; + var slides = document.getElementById('slideProj'); + var outline = document.getElementById('outlineStyle'); + slides.setAttribute('media','screen'); + outline.disabled = true; + if (isGe) { + slides.setAttribute('href','null'); // Gecko fix + slides.setAttribute('href',slideCSS); // Gecko fix + } + if (isIE && document.styleSheets && document.styleSheets[0]) { + document.styleSheets[0].addRule('img', 'behavior: url(ui/default/iepngfix.htc)'); + document.styleSheets[0].addRule('div', 'behavior: url(ui/default/iepngfix.htc)'); + document.styleSheets[0].addRule('.slide', 'behavior: url(ui/default/iepngfix.htc)'); + } +} + +function getIncrementals(obj) { + var incrementals = new Array(); + if (!obj) + return incrementals; + var children = obj.childNodes; + for (var i = 0; i < children.length; i++) { + var child = children[i]; + if (hasClass(child, 'incremental')) { + if (child.nodeName == 'OL' || child.nodeName == 'UL') { + removeClass(child, 'incremental'); + for (var j = 0; j < child.childNodes.length; j++) { + if (child.childNodes[j].nodeType == 1) { + addClass(child.childNodes[j], 'incremental'); + } + } + } else { + incrementals[incrementals.length] = child; + removeClass(child,'incremental'); + } + } + if (hasClass(child, 'show-first')) { + if (child.nodeName == 'OL' || child.nodeName == 'UL') { + removeClass(child, 'show-first'); + if (child.childNodes[isGe].nodeType == 1) { + removeClass(child.childNodes[isGe], 'incremental'); + } + } else { + incrementals[incrementals.length] = child; + } + } + incrementals = incrementals.concat(getIncrementals(child)); + } + return incrementals; +} + +function createIncrementals() { + var incrementals = new Array(); + for (var i = 0; i < smax; i++) { + incrementals[i] = getIncrementals(document.getElementById('slide'+i)); + } + return incrementals; +} + +function defaultCheck() { + var allMetas = document.getElementsByTagName('meta'); + for (var i = 0; i< allMetas.length; i++) { + if (allMetas[i].name == 'defaultView') { + defaultView = allMetas[i].content; + } + if (allMetas[i].name == 'controlVis') { + controlVis = allMetas[i].content; + } + } +} + +// Key trap fix, new function body for trap() +function trap(e) { + if (!e) { + e = event; + e.which = e.keyCode; + } + try { + modifierKey = e.ctrlKey || e.altKey || e.metaKey; + } + catch(e) { + modifierKey = false; + } + return modifierKey || e.which == 0; +} + +function startup() { + defaultCheck(); + if (!isOp) createControls(); + slideLabel(); + fixLinks(); + externalLinks(); + fontScale(); + if (!isOp) { + notOperaFix(); + incrementals = createIncrementals(); + slideJump(); + if (defaultView == 'outline') { + toggle(); + } + document.onkeyup = keys; + document.onkeypress = trap; + document.onclick = clicker; + } +} + +window.onload = startup; +window.onresize = function(){setTimeout('fontScale()', 50);} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/i18n/00_head.txt Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,8 @@ +<!-- style sheet links --> +<link rel="stylesheet" href="ui/i18n/slides.css" type="text/css" media="projection" id="slideProj" /> +<link rel="stylesheet" href="ui/default/outline.css" type="text/css" media="screen" id="outlineStyle" /> +<link rel="stylesheet" href="ui/default/print.css" type="text/css" media="print" id="slidePrint" /> +<link rel="stylesheet" href="ui/default/opera.css" type="text/css" media="projection" id="operaFix" /> + +<!-- S5 JS --> +<script src="ui/default/slides.js" type="text/javascript"></script>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/i18n/framing.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,23 @@ +/* The following styles size and place the slide components. + Edit them if you want to change the overall slide layout. + The commented lines can be uncommented (and modified, if necessary) + to help you with the rearrangement process. */ + +div#header, div#footer, .slide {width: 100%; top: 0; left: 0;} +div#header {top: 0; left: 0; z-index: 1;} +div#footer {top: auto; bottom: 0; width: 100%; z-index: 5;} +.slide {top: 0; width: 88%; padding: 1em 7% 2em 5%; z-index: 2;} + +div#controls {bottom: 1em; left: 0; width: 100%; text-align: center; z-index: 1000;} +div#controls form {margin: 0; padding: 0;} + +#currentSlide {position: absolute; left: 0; bottom: 0.5em; z-index: 10; + width: 100%; text-align: center;} +html>body #currentSlide {position: fixed;} + +/* +div#header {background: #FCC;} +div#footer {background: #CCF;} +div#controls {background: #BBD;} +div#currentSlide {background: #FFC;} +*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/i18n/pretty.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,44 @@ +/* + Theme: i18n + Eric A. Meyer (http://meyerweb.com/) + Theme placed under CC by-sa 2.0 license +*/ + +body {background: #95A7D4 url(bg-slide.jpg) 100% 100% no-repeat; color: #210; font: 28px Arial, sans-serif;} +a {text-decoration: none; color: #336; border-bottom: 1px dotted;} +h1, h2, h3, h4, h5, h6 {font-size: 1em; margin: 0;} +sup {font-size: 0.75em; font-weight: normal; + vertical-align: 0.5em; line-height: 1px;} +ul {margin-left: 1em; padding-left: 0;} +li {margin-bottom: 0.66em;} +li li {margin: 0.33em 0; font-size: smaller;} + +#header {background: url(bg-shade.png); border-bottom: 1px solid #333; + padding-bottom: 2em;} +#footer {background: url(bg-shade.png); color: #BBB; border-top: 1px solid #333;} +#header, #footer {font-size: 0.5em;} +#footer h1, #footer h2 { padding: 0.5em 0.75em; + font-weight: normal; font-style: italic;} +#footer h1 {left: 0; font-size: 1em; letter-spacing: 1px;} +#footer h2 {position: absolute; bottom: 0; right: 0;} + +#controls {font-size: 0.75em;} +#navList {margin-top: 3px;} +#navLinks a {margin: 0 0.33em; padding: 0 0.25em; + border: 1px solid; border-color: #CCD #556 #556 #CCD; + background-color: #8597C4;} + +#currentSlide {font-size: 0.5em;} +#currentSlide span {font-size: 13px; color: rgb(49%,47%,66%);} +#currentSlide #csSep {display: none;} +#currentSlide #csHere {font-weight: bold;} +#currentSlide #csHere:before {content: "#"; font-weight: normal;} +#currentSlide #csTotal:before {content: " of ";} + +.slide h1 {font-size: 1.66em; line-height: 1; letter-spacing: -1px; + margin: 0 -15% 1em 0; padding: 0.5em 15% 0.06125em 0; border-bottom: 0.06125em solid rgb(90,94,120);} +#slide0 h1 {border: none; font-size: 2.25em; letter-spacing: 0; margin: 3em 0 1.5em;} +#slide0 h3 {margin: 0.5em 0 0;} +#slide0 h4 {margin-top: 0; font-size: smaller;} + +.slide .current {color: #003; text-shadow: 0 0 0.25em #9AABD7;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/i18n/s5-core.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,9 @@ +/* Do not edit or override these styles! The system will likely break if you do. */ + +div#header, div#footer, div#controls, div.slide {position: absolute;} +html>body div#header, html>body div#footer, + html>body div#controls, html>body div.slide {position: fixed;} +.handout {display: none;} +.layout {display: block;} +div.slide, .hideme, .incremental {visibility: hidden;} +#slide0 {visibility: visible;}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/ui/i18n/slides.css Thu Jan 06 22:35:43 2011 +0900 @@ -0,0 +1,3 @@ +@import url(s5-core.css); /* required to make the slide show run at all */ +@import url(framing.css); /* sets basic placement and size of slide components */ +@import url(pretty.css); /* stuff that makes the slides look better than blah */ \ No newline at end of file