Preface
This tutorial presumes that you have R, R Studio, and SQLite installed, although to be technically accurate, you do actually need to have SQLite installed if you are connected from R as the RSQLite package contains all necessary code to open a SQLite database file.
Follow the tutorial by starting your own R Notebook in R Studio. If you do not already have R and/or R Studio you will need to download and install them. You must first install R from R Project and then the R Studio IDE from R Studio. Alternatively, rather than installing R and R Studio locally, you can do the tutorial using R Studio Cloud.
Introduction
This is an R Markdown Notebook. When you execute code within the notebook, the results appear beneath the code. It demonstrates how to work with data frames, one of the most important R data types for data processing in addition to vector and scalars.
The tutorial is geared towards students in information science, data science, and database design. It demonstrates basic syntax in R that are most often used for data processing rather than statistics.
Execute chunks by clicking the Run button within the chunk or by placing your cursor inside it and pressing Ctrl+Shift+Enter. The code runs in the order in which the chunks are executed, so non-linear code execution is possible unless you instruct R Studio to run all chunks starting at the first chunk.
Add a new chunk by clicking the Insert Chunk button on the toolbar or by pressing Ctrl+Alt+I.
When you save the notebook, an HTML file containing the code and output will be saved alongside it (click the Preview button or press Ctrl+Shift+K to preview the HTML file).
The preview shows you a rendered HTML copy of the contents of the editor. Consequently, unlike Knit, Preview does not run any R code chunks. Instead, the output of the chunk when it was last run in the editor is displayed.
Working in R
To write “programs” in R you will need Base R which you can download for Linux, MacOS, and Windows from R Project. This is the core language with an interactive console. Programs, or more aptly R scripts, can be built in any text editor (TextEdit, Notepad, vi, Sublime, JEdit, etc.).
R doesn’t really have “programs” in the traditional sense. There is no “compiling”; programs are “scripts” that are interpreted. It is possible to execute R scripts from the command line and thus have them behave like programs but most work is done in R Notebooks that are chunks of code.
Most programming is done with an IDE (Integrated Development Environment). The most common is R Studio downloadable from RStudio. There hosted version of R Studio available at rstudio.cloud.
The tutorial below explains how to get started with R Notebooks:
Basic R
R is a scripted language which means that you do not need to compile the program before running it. Statements and expressions are executed as you type them.
R Code Chunks
We will only discuss how to write R “programs” using an R Notebook in R Studio. Programs in R run from start to end. Each chunk should be a step in your analysis or data project. Name your code chunk, so you can quickly navigate to them.
In the chunk below, the variable cars passed to the built-in Base R function plot
is one of the dozens of “built-in” data frames; a data frame being data arranged in rows and columns similar to a spreadsheet or CSV file.
Note that you call a function by using the function’s name followed by the arguments you wish to pass to the function. Of course, you need to follow the definition of the function. Many functions are simply “built-in” while others come from packages that you need to explicitly load into your program.
Note that there is no semicolon at the end of a line.
```{r namedChunk, eval=FALSE}
plot(x = mtcars$mpg, y = mtcars$hp)
```
Expressions
R can be directly used to solve simple or complex mathematical expressions.
# [1] in the above answer indicates the index of your results.
# R always shows the result with index for each row.
((2^3)*5)-1
## [1] 39
# sqrt and exp are built-in functions in R for finding Square root and exponential respectively.
sqrt(4)* exp(2)
## [1] 14.77811
Variables and Identifiers
Holding a value in a variable is done through assignment. Once you assign a value to a variable, the variables becomes an R object. There are two ways to do an assignment, using ‘=’ or with ‘<-’. The latter is the preferred way in R but the former might be more familiar to those programmers coming to R from Java, C++, or Python.
Note that variables are explicitly defined or declared. The first time a variable is assigned a value defines the variable and its type. The type is based on the value that is assigned. Unlike other programming languages such as C++, C#, or Java, R is not strongly typed: the type of a variable can change when a value of a different type is assigned. A variable can be used in an expression. Its value can be inspected by just using the variable by itself.
The value of a variable can be displayed either by using the variable by itself or using the print()
function.
# assignment with '=' of a number
x = 12
# inspect (print/display) the value
x
## [1] 12
# assignment a new value and change its type to "text"
x = "Hello"
x
## [1] "Hello"
# assignment with '<-'
x <- 12
print(x)
## [1] 12
The rules for naming an identifier (variable, function, or package name) for an object are as follows:
identifiers are case-sensitive and cannot contain spaces or special characters such as #, %, $, @, *, &, ^, !, ~ an identifier must start with a letter, but may contain any combination of letters and digits thereafter special characters dot (.) and underscore (_) are allowed
The dot (.) is a regular character in R and that can be confusing as other language (e.g., Java) use dot to designate property or method access, e.g, in Java x.val means that you are accessing the val property of the object x.
Some examples of legal variable names are: df, df2, df.txns, df_all2017. These are some illegal variable names: 2df (cannot start with a digit), rs$all (cannot contain a $; the $ is used to access columns in a dataframe), rs# (only . and _ are allowed in addition to digits and letters).
It is considered good programming practice to give identifiers a sensible name that hints as to what is stored in the variable rather than using random name like x, val, or i33. Identifiers should be named consistently. Many programmers use one of two styles:
- underscores, e.g., interest_rate
- camelCase, e.g., squareRoot, graphData, currentWorkingDirectory
Note that R is case sensitive which means that R treats the identifiers AP and ap as different objects. As a side note, files may also be case sensitive but that depends on the operating system. MacOS and Linux are case sensitive, while Windows is case aware but not case sensitive. For example, on MacOS and Linux there is a difference between “AirPassengers.txt” and “airpassengers.txt” while on Windows there is not. SQL is also not case sensitive. It is a best practice to assume case sensitivity.
Built-in Data Frames
There are numerous data frames built into R that are accessible without loading them first from external files. These data frames are for experimentation and learning and not for actual analytics work. One such built-in data frame is mtcars
. To get a list of all built-in data frames, run data()
.
## mpg cyl disp hp drat wt qsec vs am gear carb
## Mazda RX4 21.0 6 160.0 110 3.90 2.620 16.46 0 1 4 4
## Mazda RX4 Wag 21.0 6 160.0 110 3.90 2.875 17.02 0 1 4 4
## Datsun 710 22.8 4 108.0 93 3.85 2.320 18.61 1 1 4 1
## Hornet 4 Drive 21.4 6 258.0 110 3.08 3.215 19.44 1 0 3 1
## Hornet Sportabout 18.7 8 360.0 175 3.15 3.440 17.02 0 0 3 2
## Valiant 18.1 6 225.0 105 2.76 3.460 20.22 1 0 3 1
## Duster 360 14.3 8 360.0 245 3.21 3.570 15.84 0 0 3 4
## Merc 240D 24.4 4 146.7 62 3.69 3.190 20.00 1 0 4 2
## Merc 230 22.8 4 140.8 95 3.92 3.150 22.90 1 0 4 2
## Merc 280 19.2 6 167.6 123 3.92 3.440 18.30 1 0 4 4
## Merc 280C 17.8 6 167.6 123 3.92 3.440 18.90 1 0 4 4
## Merc 450SE 16.4 8 275.8 180 3.07 4.070 17.40 0 0 3 3
## Merc 450SL 17.3 8 275.8 180 3.07 3.730 17.60 0 0 3 3
## Merc 450SLC 15.2 8 275.8 180 3.07 3.780 18.00 0 0 3 3
## Cadillac Fleetwood 10.4 8 472.0 205 2.93 5.250 17.98 0 0 3 4
## Lincoln Continental 10.4 8 460.0 215 3.00 5.424 17.82 0 0 3 4
## Chrysler Imperial 14.7 8 440.0 230 3.23 5.345 17.42 0 0 3 4
## Fiat 128 32.4 4 78.7 66 4.08 2.200 19.47 1 1 4 1
## Honda Civic 30.4 4 75.7 52 4.93 1.615 18.52 1 1 4 2
## Toyota Corolla 33.9 4 71.1 65 4.22 1.835 19.90 1 1 4 1
## Toyota Corona 21.5 4 120.1 97 3.70 2.465 20.01 1 0 3 1
## Dodge Challenger 15.5 8 318.0 150 2.76 3.520 16.87 0 0 3 2
## AMC Javelin 15.2 8 304.0 150 3.15 3.435 17.30 0 0 3 2
## Camaro Z28 13.3 8 350.0 245 3.73 3.840 15.41 0 0 3 4
## Pontiac Firebird 19.2 8 400.0 175 3.08 3.845 17.05 0 0 3 2
## Fiat X1-9 27.3 4 79.0 66 4.08 1.935 18.90 1 1 4 1
## Porsche 914-2 26.0 4 120.3 91 4.43 2.140 16.70 0 1 5 2
## Lotus Europa 30.4 4 95.1 113 3.77 1.513 16.90 1 1 5 2
## Ford Pantera L 15.8 8 351.0 264 4.22 3.170 14.50 0 1 5 4
## Ferrari Dino 19.7 6 145.0 175 3.62 2.770 15.50 0 1 5 6
## Maserati Bora 15.0 8 301.0 335 3.54 3.570 14.60 0 1 5 8
## Volvo 142E 21.4 4 121.0 109 4.11 2.780 18.60 1 1 4 2
mtcars
and mtcars
print out the first and last six rows of a data frame, respectively. You can specify the number of rows to display.
## mpg cyl disp hp drat wt qsec vs am gear carb
## Mazda RX4 21.0 6 160 110 3.90 2.620 16.46 0 1 4 4
## Mazda RX4 Wag 21.0 6 160 110 3.90 2.875 17.02 0 1 4 4
## Datsun 710 22.8 4 108 93 3.85 2.320 18.61 1 1 4 1
## Hornet 4 Drive 21.4 6 258 110 3.08 3.215 19.44 1 0 3 1
## Hornet Sportabout 18.7 8 360 175 3.15 3.440 17.02 0 0 3 2
## Valiant 18.1 6 225 105 2.76 3.460 20.22 1 0 3 1
## mpg cyl disp hp drat wt qsec vs am gear carb
## Porsche 914-2 26.0 4 120.3 91 4.43 2.140 16.7 0 1 5 2
## Lotus Europa 30.4 4 95.1 113 3.77 1.513 16.9 1 1 5 2
## Ford Pantera L 15.8 8 351.0 264 4.22 3.170 14.5 0 1 5 4
## Ferrari Dino 19.7 6 145.0 175 3.62 2.770 15.5 0 1 5 6
## Maserati Bora 15.0 8 301.0 335 3.54 3.570 14.6 0 1 5 8
## Volvo 142E 21.4 4 121.0 109 4.11 2.780 18.6 1 1 4 2
## mpg cyl disp hp drat wt qsec vs am gear carb
## Mazda RX4 21.0 6 160 110 3.90 2.620 16.46 0 1 4 4
## Mazda RX4 Wag 21.0 6 160 110 3.90 2.875 17.02 0 1 4 4
## Datsun 710 22.8 4 108 93 3.85 2.320 18.61 1 1 4 1
Accessing Rows, Columns, and Elements (Cells) of a Data Frame
Data frames are very similar to tables in relational databases and spreadsheets. They have rows and columns and the intersection of a row and column is a cell (or element). The order of access is row followed by column, e.g, the third element in the fourth row of the data frame mtcars
is mtcars[4,3]
. Note that this is reversed from the way Excel and other spreadsheets work. The <-
is the operator for assignment, although =
also works. We will see and use both.
To display a value, either use the print
function or just use the variable by itself. To print multiple items, use the paste0
function.
v <- mtcars[4,3]
x = mtcars[4,3]
print(paste0("v = ",v," and x = ",x))
## [1] "v = 258 and x = 258"
Leaving out a dimension (row or column) accesses the entire row or column. The resultant is a data frame with a single row. Often the values must be converted to a vector data type. Conversions of variables from one type to another is done with the family of as.xxxx
functions, e.g., as.vector
, as.numeric
, or as.factor
. Vectors can contain numeric or character data but all elements must be of the same type. In R, a list is similar to a vector but it may contain a mix of elements. A matrix is similar to a data frame but it can only contain numbers and it can have more than two dimensions.
Some functions expect data frames, some vectors, some lists. You need to read the documentation of a function to find out. Furthermore, some functions will automatically convert (also called coerce) a variable from one type to the one it requires.
You can also access a column in data frame by its column name. For an entire column you either use the columns position or its name: df[,column]
or df$columnName
.
# all of row 4; the result is a data frame
r <- mtcars[4,]
sum(r)
## [1] 426.135
## [1] 108
mtcars[c(1,4)] # columns 1 and 4 as a new dataframe
## mpg hp
## Mazda RX4 21.0 110
## Mazda RX4 Wag 21.0 110
## Datsun 710 22.8 93
## Hornet 4 Drive 21.4 110
## Hornet Sportabout 18.7 175
## Valiant 18.1 105
## Duster 360 14.3 245
## Merc 240D 24.4 62
## Merc 230 22.8 95
## Merc 280 19.2 123
## Merc 280C 17.8 123
## Merc 450SE 16.4 180
## Merc 450SL 17.3 180
## Merc 450SLC 15.2 180
## Cadillac Fleetwood 10.4 205
## Lincoln Continental 10.4 215
## Chrysler Imperial 14.7 230
## Fiat 128 32.4 66
## Honda Civic 30.4 52
## Toyota Corolla 33.9 65
## Toyota Corona 21.5 97
## Dodge Challenger 15.5 150
## AMC Javelin 15.2 150
## Camaro Z28 13.3 245
## Pontiac Firebird 19.2 175
## Fiat X1-9 27.3 66
## Porsche 914-2 26.0 91
## Lotus Europa 30.4 113
## Ford Pantera L 15.8 264
## Ferrari Dino 19.7 175
## Maserati Bora 15.0 335
## Volvo 142E 21.4 109
mtcars[,2] # all of column 2
## [1] 6 6 4 6 8 6 8 4 4 6 6 8 8 8 8 8 8 4 4 4 4 8 8 8 8 4 4 4 8 6 8 4
mtcars[5:7,] # rows 5 to 7 as a new dataframe
## mpg cyl disp hp drat wt qsec vs am gear carb
## Hornet Sportabout 18.7 8 360 175 3.15 3.44 17.02 0 0 3 2
## Valiant 18.1 6 225 105 2.76 3.46 20.22 1 0 3 1
## Duster 360 14.3 8 360 245 3.21 3.57 15.84 0 0 3 4
mtcars$cyl # column named "cyl"
## [1] 6 6 4 6 8 6 8 4 4 6 6 8 8 8 8 8 8 4 4 4 4 8 8 8 8 4 4 4 8 6 8 4
mtcars$cyl[2] # 2nd row in the column "cyl"
## [1] 6
mtcars$cyl[3:9] # rows 3 to 9 for column "cyl" as a vector
## [1] 4 6 8 6 8 4 4
## [1] 20.09062
Aggregation and Statistical Functions
As a language with its origin in statistics and statistical data processing, R has a plethora of statistical functions. Some of the most important functions for data processing are shown below. Consult online documentation and statistics references for more information, e.g., How To Get Descriptive Statistics In R and Base R Statistical Functions.
# import data for descriptive statistics, the built-in data frame 'warpbreaks'
data(warpbreaks)
# summary descriptive statistics
summary(warpbreaks)
## breaks wool tension
## Min. :10.00 A:27 L:18
## 1st Qu.:18.25 B:27 M:18
## Median :26.00 H:18
## Mean :28.15
## 3rd Qu.:34.00
## Max. :70.00
There are thousands of functions across hundreds of packages (external libraries of functions written for specific purposes, e.g., data mining, statistical inference, machine learning, image processing, web development, visualization, XML processing, SQL, and so forth). You will learn them over time – and it’s unlikely you will ever learn all of them, so have patience. For a package to be usable in an R project it must be installed; installation is done once. Then every time you need an installed package in some R code, you must load it using the library
function.
The psych library (aka package) is particularly useful for statistical analysis of data.
# import the psych package -- if this fails, then first install the package by uncommenting the next line
#install.packages("psych")
library(psych)
# detailed descriptive statistics
describe(warpbreaks)
## vars n mean sd median trimmed mad min max range skew kurtosis
## breaks 1 54 28.15 13.20 26.0 26.41 11.86 10 70 60 1.24 1.33
## wool* 2 54 1.50 0.50 1.5 1.50 0.74 1 2 1 0.00 -2.04
## tension* 3 54 2.00 0.82 2.0 2.00 1.48 1 3 2 0.00 -1.56
## se
## breaks 1.80
## wool* 0.07
## tension* 0.11
It is not unusual that data is divided into groups and that you may want categorical statistics for it. The aggregate
function is among the easiest methods of doing that. The dataset warpbreaks has data for two different kinds of wool, A and B. Using the aggregate
function you can calculate statistics for each wool separately. This is similar to a GROUP BY clause in SQL.
# Aggregate Function Example: Summary Statistics by Group
aggregate(breaks~tension , data= warpbreaks, mean)
## tension breaks
## 1 L 36.38889
## 2 M 26.38889
## 3 H 21.66667
Installing and Loading Packages
Installing Packages
To ensure that packages are automatically installed, you can use the followign code. That way your code becomes portable.
if("RSQLite" %in% rownames(installed.packages()) == FALSE) {
install.packages("RSQLite")
}
library("RSQLite")
In the above code the function installed.packages()
returns a list of the names of all installed packages. The operator %in%
is a set operator that checks if “RSQLite” is one of the returned names. If it is, the Boolean expression evaluates to \(TRUE\), otherwise \(FALSE\). If it is false, then it means the package is not installed and the optional code that installs the package is executed. The way, the loading of the package with library(“RSQLite”)
cannot fail.
Simple Plotting and Visual Data Exploration
Scatter Plot
plot(x = warpbreaks$breaks, y = warpbreaks$tension)
Q-Q Plot for Normality Checking
A 45 degree line indicates a normal distribution of the data, while a “hockey stick” curve indicates a non-normal or skewed distribution. The column below is “reasonably” normally distributed. The second QQ Plot, plots the log-transformed values which better fit a normal (Gaussian) distribution.
qqnorm(warpbreaks$breaks)
qqnorm(log(warpbreaks$breaks))
Note that the gplot2 package provide much more sophisticated visualization mechanisms and should be used in practice to produce plots for publication.
Data Frame Dimensions and Structure
## [1] 32
## [1] 11
## 'data.frame': 32 obs. of 11 variables:
## $ mpg : num 21 21 22.8 21.4 18.7 18.1 14.3 24.4 22.8 19.2 ...
## $ cyl : num 6 6 4 6 8 6 8 4 4 6 ...
## $ disp: num 160 160 108 258 360 ...
## $ hp : num 110 110 93 110 175 105 245 62 95 123 ...
## $ drat: num 3.9 3.9 3.85 3.08 3.15 2.76 3.21 3.69 3.92 3.92 ...
## $ wt : num 2.62 2.88 2.32 3.21 3.44 ...
## $ qsec: num 16.5 17 18.6 19.4 17 ...
## $ vs : num 0 0 1 1 0 1 0 1 1 1 ...
## $ am : num 1 1 1 0 0 0 0 0 0 0 ...
## $ gear: num 4 4 4 3 3 3 3 4 4 4 ...
## $ carb: num 4 4 1 1 2 1 4 2 2 4 ...
mtcars[nrow(mtcars),] # last row only of a data frame
## mpg cyl disp hp drat wt qsec vs am gear carb
## Volvo 142E 21.4 4 121 109 4.11 2.78 18.6 1 1 4 2
Adding and Removing Columns from a Data Frame
To add a new column, you simply “access” the column or use a new name for the column. Note in the example below that you can operate on entire columns (as vectors) and the operation is applied to each pair of values in the two vectors in the operation. This is much more efficient than using loops as is necessary in other programming languages.
# copy the data frame mtcars to a new data frame df
df <- mtcars
# create a new column "dispcyl" which is the displacement per cylinder
df$dispcyl <- df$disp / df$cyl
head(df)
## mpg cyl disp hp drat wt qsec vs am gear carb dispcyl
## Mazda RX4 21.0 6 160 110 3.90 2.620 16.46 0 1 4 4 26.66667
## Mazda RX4 Wag 21.0 6 160 110 3.90 2.875 17.02 0 1 4 4 26.66667
## Datsun 710 22.8 4 108 93 3.85 2.320 18.61 1 1 4 1 27.00000
## Hornet 4 Drive 21.4 6 258 110 3.08 3.215 19.44 1 0 3 1 43.00000
## Hornet Sportabout 18.7 8 360 175 3.15 3.440 17.02 0 0 3 2 45.00000
## Valiant 18.1 6 225 105 2.76 3.460 20.22 1 0 3 1 37.50000
Create a New Data Frame
Data frames are created in various ways: use the <code<>data.frame function, load a CSV file, execute a SQL query, or as a result of many package functions.
Load a Data Frame from CSV
Quick note: Capitalization in path and file names does not matter in Windows, but does matter on MacOS and Linux. Furthermore, note that even in Windows the path delimiter is a forward slash / and not the usual backwards slash \. The \ is an “escape” character and used to inject non-printable characters into a string (text), e.g., “This string contains”quotes”.” which would be written in R as “this string contains \”quotes\“.”
Also, the parameters header = F
instructs read.csv
not to interpret the first line as header labels. Of course, if there are no labels, then you need to define your own.
Aside from CSV files, R can also load a number of other file format using various packages, including XML, Excel, SPSS, MatLab, among many others.
df <- read.csv(file = "customertxndata.csv", header = F)
head(df)
df <- read.csv(file = "customertxndata.csv",
header = F,
col.names = c("numVisits","NumTxn","OS","Gender","TotSp"))
head(df)
Note that the value of the ‘Male’ column in the first row is NA which is the way that R indicates a missing data value. It is not 0 or an empty string, it is unknown. So, statistical functions and algebraic operations would result in an NA as well.
Strings vs Factors
The factor data type encodes categorical data, e.g., the value of a variable is one of a fixed value set. Many statistical functions in R require categorical variables to be of type factor. However, often, during data processing, we need the actual text rather than having it encoded as a factor (which is actually stored in R as an integer for efficiency). So, when reading a CSV file you need to decide if you want text columns to be character strings or factors by setting the stringsAsFactors
parameter.
You may use either F
and T
or FALSE
and TRUE
.
df <- read.csv(file = "customertxndata.csv",
header = F,
stringsAsFactors = FALSE,
col.names = c("numVisits","NumTxn","OS","Gender","TotSp"))
head(df)
Create a New Data Frame
The code below creates a new data frame from column vectors. Notice how the column names are the names of the vectors. A new vector is created with the c
function, e.g., v <- c(3,5,1,9)
.
df1 <- data.frame(state = c('Arizona','Georgia', 'New York','Indiana','Washington','Texas'),
code = as.factor(c('AZ','GA','NY','IN','WA','TX')),
score = c(62,47,55,74,31,85))
head(df1)
## state code score
## 1 Arizona AZ 62
## 2 Georgia GA 47
## 3 New York NY 55
## 4 Indiana IN 74
## 5 Washington WA 31
## 6 Texas TX 85
Search Data Frames
There are two important functions for “searching” data frames: which
and any
. The code below uses the built-in Orange data frame which contains measurements of orange trees. It has three columns: the tree, the age of the tree (days since 1968/12/31), and circumference (in mm).
which
## Grouped Data: circumference ~ age | Tree
## Tree age circumference
## 1 1 118 30
## 2 1 484 58
## 3 1 664 87
## 4 1 1004 115
## 5 1 1231 120
## 6 1 1372 142
# find all rows where the circumference is more than 200mm
rs <- which(df$circumference > 200)
# display all rows where the circumference is more than 200mm
df[rs,]
## Grouped Data: circumference ~ age | Tree
## Tree age circumference
## 13 2 1372 203
## 14 2 1582 203
## 27 4 1372 209
## 28 4 1582 214
# compound conditions are possible with & (and), | (or), and ! (not)
rs2 <- which(df$circumference > 200 & df$age < 1500)
rs3 <- which(df$circumference < 200 | !(df$age < 1500))
rs4 <- which(df$circumference > 400 | df$age > 1500)
rs2
## [1] 13 27
## [1] 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26
## [26] 28 29 30 31 32 33 34 35
## [1] 7 14 21 28 35
## [1] 1582
## [1] 894.8788
In the above example rs <- which(df$circumference > 200)
finds all rows in the data frame df where circumference > 200. The rows are saved in rs.
any
The any
function returns \(TRUE\) or \(FALSE\) depending on whether any column (or row) in the dataframe satisfies a Boolean expression.
# is there any tree with age > 2000?
any(df$age > 25)
## [1] TRUE
Using SQL with Data Frames
The package sqldf allows you to use SQL to access, process, search, and aggregate data in data frames. The sqldf package actually loads the data frame into an in-memory SQLite database.
For more information on sqldf, consult Manipulate R Data Frames Using SQL
The tidyverse package also contains numerous functions for processing data frames in a SQL-like manner.
#install.packages("sqldf")
library(sqldf)
## Loading required package: gsubfn
## Loading required package: proto
## Warning in doTryCatch(return(expr), name, parentenv, handler): unable to load shared object '/Library/Frameworks/R.framework/Resources/modules//R_X11.so':
## dlopen(/Library/Frameworks/R.framework/Resources/modules//R_X11.so, 0x0006): Library not loaded: /opt/X11/lib/libSM.6.dylib
## Referenced from: <FFA47D77-8F35-36FC-B0E5-38351B8D9512> /Library/Frameworks/R.framework/Versions/4.3-arm64/Resources/modules/R_X11.so
## Reason: tried: '/opt/X11/lib/libSM.6.dylib' (no such file), '/System/Volumes/Preboot/Cryptexes/OS/opt/X11/lib/libSM.6.dylib' (no such file), '/opt/X11/lib/libSM.6.dylib' (no such file), '/Library/Frameworks/R.framework/Resources/lib/libSM.6.dylib' (no such file), '/Library/Java/JavaVirtualMachines/jdk-11.0.18+10/Contents/Home/lib/server/libSM.6.dylib' (no such file)
## tcltk DLL is linked to '/opt/X11/lib/libX11.6.dylib'
## Could not load tcltk. Will use slower R code instead.
# perform SQL queries on the built-in 'iris' data frame
sqldf("select * from iris limit 5")
## Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1 5.1 3.5 1.4 0.2 setosa
## 2 4.9 3.0 1.4 0.2 setosa
## 3 4.7 3.2 1.3 0.2 setosa
## 4 4.6 3.1 1.5 0.2 setosa
## 5 5.0 3.6 1.4 0.2 setosa
sqldf("select count(*) from iris")
## count(*)
## 1 150
sqldf("select Species, count(*) from iris group by Species")
## Species count(*)
## 1 setosa 50
## 2 versicolor 50
## 3 virginica 50
# note that each sqldf query actually returns a data frame
rs <- sqldf("select Species, count(*) as num from iris group by Species")
mean(rs$num)
## [1] 50
Load Data from a Database via SQL
To read data from a database into R, follows these steps:
- open connection to database
- build SQL query
- execute SQL query by sending to database
- capture result in dataframe
Connecting to a database is done in a database-specific way and each database is different. Packages specific to the database need to be loaded (of course, after installation). The code below assumes that the package RSQLite for connecting to SQLite databases is installed but not loaded. To use SQLite from R does not actually require that SQLite is downloaded and installed.
To connect to a database you need to know where the database is located. For most client/server databases like MySQL you need to know the server’s IP address on which the database runs. For SQLite you need the database file path (as SQLite does run not on an actual remote server).
To run a query (retrieve data) you most commonly use the dbGetQuery
function. To perform an INSERT, UPDATE, DELETE, CREATE TABLE, DROP TABLE, ALTER TABLE you need to use dbSendQuery
.
The example below performs a direct connect to the database and uses functions to retrieve data from the database via SQL. This is an alternative to embedding SQL chunks ({sql}) in an R Notebook.
library(RSQLite)
# connect to the SQLite database in the specified file
db.conn <- dbConnect(SQLite(), dbname="CoffeeDB.sqlitedb")
# construct a SQL query
sqlCmd = "SELECT * FROM coffees"
# send the SQL query to the database
rs = dbGetQuery(db.conn, sqlCmd)
# print part of the result table
head(rs,3)
## id coffee_name price
## 1 1 Colombian 7.99
## 2 2 French_Roast 8.99
## 3 3 Espresso 9.99
Example: Compute Sum of Numbers
Problem Statement
Given a vector (or array) of numbers, calculate the sum of those numbers. Solve the problem first using loops and then using recursion. Write a function and then call the function. The function should ignore any non-numeric elements.
Test Cases
- Given the vector <2,6,1,0,-4,99>, the function should return 104.
- Given an empty vector <>, the function should return NA.
- Given the vector <2,6,1,‘11’>, the function should return 9.
- Given the vector <‘2’,‘Two’,’‘,’11’>, the function should return 0.
- Given the empty vector <>, the function should return 0.
Sample Solution
Let’s start by working out the algorithm for only numbers and not (yet) using a function. We can calculate the sum by adding each number to some “accumulator” variable, e.g., the sum of <2,6,1> is x = 2, x = x + 6, x = x + 1. In this example, x is the accumulator variable. Using an accumulator is a common practice in these types of problems. The accumulator could either start at 0 or at the first element. Having it start at 0 is simpler because it would account for an empty vector that doesn’t have a first element.
When you write x = x + 1, remember that the evaluation of = is from right to left, i.e., the right side is evaluated first and then the value of the result of that expression is assigned to the variable on the left side. Let’s say that x = 5 before you write the aforementioned statement. So, the expression x + 1 is 5 + 1 which evaluates to 6. That value is then assigned to x, so after that x = 6.
v = c(3, 6, 1) # a vector/array of numbers
x = 0 # x is our accumulator; it starts at 0
# loop through each element of the vector
for (i in 1:length(v)) {
# add the next element in the vector to x
x = (x + v[i])
}
print (x)
## [1] 10
What would happen if the vector is empty? Test the above code. Note that it still works if v = c()
. Test it with negative numbers in the vector. It still works. But what about strings? Now it fails. So, we need to improve the program to ignore negative numbers. All programming languages have some way of guarding against that. Some languages like Java and C++ require that all elements of a vector are of the same declared type, so adding a string would cause a compile-time error. No worries in those languages. But untyped and uncompiled languages like R, Python, and JavaScript require run-time checks. So, let’s add one. We need a function that checks the type of a variable. R has functions such as is.numeric
for that purpose.
But there is another problem. Vectors in R are of a single type, i.e., all elements must be of the same type. R attempts to coerce (aka cast) the elements in the vector to a common type. Since a string cannot be converted to a number, it’ll convert the numbers to text. Try it out: what is the value of v[1]? It’s “3” – a string. So, we need to convert each element to a number and ignore the number it fails. as.numeric
will attempt a conversion of any text containing a number to a number, e.g. it will convert “3” to 3 and “3.14” to 3.14. Again, if you are in doubt or are not sure, try it out – experiment. In fact, create a new Notebook or just open up the R console and type in the statements; see what happens.
v = c(3, 6, "two", 1)
print(v[1])
## [1] "3"
## [1] 3
## Warning in print(as.numeric(v[3])): NAs introduced by coercion
## [1] NA
So, if the conversion to a number is not possible, it will return NA. NA is similar to null or nil in many other languages. We can check of a value is NA by using the function is.na
; we cannot simply say if (v[i] == NA)
– NA is not a value so you cannot use the comparison operator. Many other languages work the same way.
v = c(3, 6, "two", 1)
x = 0 # x is our accumulator; it starts at 0
# loop through each element of the vector
for (i in 1:length(v)) {
# attempt to convert the text to a number
k = as.numeric(v[i])
# add the next element in the vector to x if it's not NA
if (!is.na(k))
x = (x + k)
}
print (x)
## [1] 10
Does our code still work if the vector is all numbers? What if it’s all strings? Let’s check that. Remember to always test prior test cases to ensure that some new code did not break your old code. Software developers call that regression testing.
v = c(3, 6, 2, 1)
x = 0 # x is our accumulator; it starts at 0
# loop through each element of the vector
for (i in 1:length(v)) {
# attempt to convert the text to a number
k = as.numeric(v[i])
# add the next element in the vector to x if it's not NA
if (!is.na(k))
x = (x + k)
}
print (x)
## [1] 12
Indeed, it still works. Now what about all text or empty… this is getting difficult without repeating code. If you find yourself copying and pasting code, it means that you need a function. Let’s put the code into a function. We’ll also add code to guard against an empty vector.
sumVector <- function (v)
{
x = 0 # x is an accumulator; it starts at 0
if (length(v) == 0)
return (0)
# loop through each element of the vector
for (i in 1:length(v)) {
# attempt to convert the text to a number
k = as.numeric(v[i])
# add the next element in the vector to x if it's not NA
if (!is.na(k))
x = (x + k)
}
return (x)
}
Quick comment on R: strings can be enclosed in either double or single quote, e.g., ‘text’ is the same as “text”. Whether you use single or double quotes depends on context. For example, if you want to use the string Bob’s Car, then you would need to enclode that in double quotes: “Bob’s Car”.
v = c(2,6,1,0,-4,99)
x = sumVector(v)
print (x)
## [1] 104
v = c(2,6,1,'11')
x = sumVector(v)
print (x)
## [1] 20
v = c()
x = sumVector(v)
print (x)
## [1] 0
v = c('2','Two','','11')
x = sumVector(v)
print (x)
## [1] 13
This takes care of our originally defined test cases. Are there test cases we forgot to account for? Can you think of other situations? What if someone passed a list or a matrix or a single number? Would it still work? In R, Python, and JavaScript, as well as other non-compiled languages, you need to add many more run-time checks.
One quick programming: the variable x in the function is local to the function and is not known or even visible outside the function. So, it’s a totally different variable than the x in the test code. This is so because R uses, like most modern languages, local scoping. Anything declared within curly braces {…} is local to that scope.
v = 99
x = sumVector(v)
print (x)
## [1] 99
v = list(3, c(34, 55, 99))
# this will not work as v is a list not the expected vector
# x = sumVector(v)
print (x)
## [1] 99
It works for single numbers but not for lists, so let’s add a check to ensure that the passed argument is a vector. Again, this is a common need for many languages: run-time type checking.
sumVector <- function (v)
{
# if v is a list or not a vector, return 0
if (!is.vector(v) || is.list(v))
return (0)
if (length(v) == 0)
return (0)
# v is a valid vector; let's add the numbers and ignore strings
x = 0 # x is an accumulator; it starts at 0
# loop through each element of the vector
for (i in 1:length(v)) {
# attempt to convert the text to a number
k = as.numeric(v[i])
# add the next element in the vector to x if it's not NA
if (!is.na(k))
x = (x + k)
}
return (x)
}
v = 99
x = sumVector(v)
print (x)
## [1] 99
v = list(3, c(34, 55, 99))
x = sumVector(v)
print (x)
## [1] 0
There is an interesting programming design argument in the above code: what is the correct return value when the passed argument is not a vector? Should it be 0 or should it be NA as it cannot be computed. Generally, returning 0 implies that the calculation was successful and evaluated to 0, but that’s not the case here, so returning NA might allow the caller of the function to catch that. In Java and C++ we might have thrown an exception, but R does not support exceptions.
Note how we built the code in stages. It was not all done at once. Start simple, keep adding to it, take care of more and more situations. Eventually you have solved the entire problem.
Native R Solution
Before we leave this example, let’s take a look at a more “native” R implementation that takes advantage of the inherent vector processing capabilities (alongside potential hardware-based vectorization of the code) and attendant significant performance improvements.
v = c(2,6,1,0,-4,99)
x = sum(v)
print (x)
## [1] 104
The solution below prints not just the sum of the elements but the sum of squares of the elements. Notice how the R implementation does not require the use of a loop because any operation on a vector is automatically carried out for each element of the vector – in effect the loop is implied.
v = c(2,6,1,0,-4,99)
x = sum(v ^ 2)
print (x)
## [1] 9858
Example: Find Time Difference
Problem Statement
Given two time values based on a 24 hour clock, determine how much time has elapsed between the first and the second time. The time is given in the format HH:MM:SS. HH is between 0 and 23, and MM and SS are between 0 and 59. Values less than 10 have a leading zero, e.g., 07:15:00. Midnight is 00:00
The output should at first be the number of seconds between the two time values. Then, the program should be improved to display the difference in the number of hours, the number of minutes, and the number of seconds that have passed from the first to the second time, in the form HH HOURS MM MINUTES SS SECONDS.
If the second time is “before” the first time, assume that it is the following day.
Test Cases
- 10:03:43 15:00:58 should display 4 HOURS 57 MINUTES 15 SECONDS
- 07:25:00 20:52:14 should display 13 HOURS 27 MINUTES 14 SECONDS
- 16:30:30 05:40:10 should display 13 HOURS 9 MINUTES 40 SECONDS
Sample Solution
Solution I
A few quick explanations on R syntax. The period (dot) is considered a valid character for identiers in R; it is not a property access operator like in Java or C++. FOr assignment, one can use =
or <-
with the latter being more common.
This solution converts each time value into seconds and then takes the difference, resulting in the time difference in seconds as long as we do not cross a day boundary.
# define two time values broken down into three variables
t1.hh = 20
t1.mm = 00
t1.ss = 00
t2.hh = 23
t2.mm = 01
t2.ss = 30
# convert each time value to all seconds
t1 = ((t1.hh * 60 * 60) + (t1.mm * 60) + t1.ss)
t2 = ((t2.hh * 60 * 60) + (t2.mm * 60) + t2.ss)
d = t2 - t1
print(d)
## [1] 10890
Solution II
In this improvement step, we will convert the result from seconds into the required format. One issue with integer division in most languages is that it will result in a fraction (floating point number). We will need to round down or coerce the result back into an integer. So, we will first find the total number of hours in the difference by dividing the difference in seconds by 360 (60 * 60 seconds per hour). The remaining seconds are then converted into minutes, and finally, the remaining seconds are left over. Perform the calculation by hand on a piece of paper and ensure that you understand our “algorithm”. In fact, using examples and working it out by hand will help you envision how you might program this.
As an aside, the calculation of the remainder could have also been done using the modulus operator; just goes to show that there is often more than one good way to solve a programming problem. Never be afraid to experiment, but start with the simplest solution first. Worry about correctness first, then about elegance and speed of execution.
In the code below, the paste()
function is used in R to concatenate strings. paste()
inserts a space between the strings, while paste0()
does not.
# define two time values broken down into three variables
t1.hh = 00
t1.mm = 30
t1.ss = 00
t2.hh = 03
t2.mm = 30
t2.ss = 30
# convert each time value to all seconds
t1 = ((t1.hh * 60 * 60) + (t1.mm * 60) + t1.ss)
t2 = ((t2.hh * 60 * 60) + (t2.mm * 60) + t2.ss)
d = t2 - t1
# find number of hours, minutes, and seconds
# convert seconds to whole hours
hh = as.integer(d / (60 * 60))
# find the remaining seconds
r = (d - (hh * (60 * 60)))
# convert seconds to whole minutes
mm = as.integer(r / 60)
# find the remaining seconds (using the mod operator this time)
ss = ( r - (mm * 60))
# format the required output
out <- paste(hh, "HOURS", mm, "MINUTES", ss, "SECONDS")
print(out)
## [1] "3 HOURS 0 MINUTES 30 SECONDS"
An issue with Solution II is that it does not consider day boundaries, so let’s work on that next. Example: What is the time difference between 23:00:00 and 03:00:00? It is exactly four hours as it’s 23h today and 3h the next morning – we are crossing days. So, how do we implement this? One approach is to check if time #1 is before or after time #2, i.e., one value is larger or smaller than the other. For the normal case, time #1 < time #2, but if the day boundary is crossed, then time #1 > time #2. If they are equal, then the difference is zero and it doesn’t matter which calculation you use. Now, when we detect that time #1 > time #2, then we need to calculate the time remaining until midnight and then the difference between midnight and the time the next day and add those two time values.
So, we have two time calculations – might be better to first define a function so we do not have duplicate code. The function will calculate the time difference and return the time difference in seconds.
Solution III
Let’s just write the function first without worrying about the day boundary crossing.
The code below makes use of the R substr()
function which extracts characters from a text string starting at one position and ending at another position. For example, substr(“abcdef”, 2, 4)
results in “bcd”. Every programming language has a similar function, although it might require an external string library. The result of an extraction from a string is a string despite being just digits – 12 is not the same as ‘12’. One is interpreted by a computer program as an integer while the other is text (a string). We need to convert. TO convert a string of digits to an integer, use as.integer()
in R; other languages have similar functions.
# FUNCTION: timeDiff (t1, t2)
# Calculates the difference between two time values in the form HH:MM:SS
# Returns the difference in seconds.
timeDiff <- function (t1, t2)
{
t1.hh = as.integer(substr(t1, 1, 2))
t1.mm = as.integer(substr(t1, 4, 5))
t1.ss = as.integer(substr(t1, 7, 8))
t2.hh = as.integer(substr(t2, 1, 2))
t2.mm = as.integer(substr(t2, 4, 5))
t2.ss = as.integer(substr(t2, 7, 8))
# convert each time value to all seconds
t1 = ((t1.hh * 60 * 60) + (t1.mm * 60) + t1.ss)
t2 = ((t2.hh * 60 * 60) + (t2.mm * 60) + t2.ss)
d = t2 - t1
return (d)
}
######## TEST CODE ########
t1 = "00:00:00"
t2 = "03:59:59"
d <- timeDiff(t1, t2)
# convert seconds to whole hours
hh = as.integer(d / (60 * 60))
# find the remaining seconds
r = (d - (hh * (60 * 60)))
# convert seconds to whole minutes
mm = as.integer(r / 60)
# find the remaining seconds (using the mod operator this time)
ss = ss = ( r - (mm * 60))
# format the required output
out <- paste(hh, "HOURS", mm, "MINUTES", ss, "SECONDS")
print(out)
## [1] "3 HOURS 59 MINUTES 59 SECONDS"
Note how we added a testing code block. Remember: always perform unit testing and test your functions.
So, now let’s deal with the day boundary crossing issue.
Solution IV
# FUNCTION: timeDiff (t1, t2)
# Calculates the difference between two time values in the form HH:MM:SS
# Returns the difference in seconds.
timeDiff <- function (t1, t2)
{
t1.hh = as.integer(substr(t1, 1, 2))
t1.mm = as.integer(substr(t1, 4, 5))
t1.ss = as.integer(substr(t1, 7, 8))
t2.hh = as.integer(substr(t2, 1, 2))
t2.mm = as.integer(substr(t2, 4, 5))
t2.ss = as.integer(substr(t2, 7, 8))
# convert each time value to all seconds
t1.secs = ((t1.hh * 60 * 60) + (t1.mm * 60) + t1.ss)
t2.secs = ((t2.hh * 60 * 60) + (t2.mm * 60) + t2.ss)
# is t1 < t2?
if (t1.secs <= t2.secs) {
d = t2.secs - t1.secs
} else {
# we are crossing a day boundary, so let's find the time
# until midnight and then the time from midnight to
# the second time; note the recursive call and adding
# one extra second since we are going until the time
# that is one minute before midnight as midnight is
# 00:00:00 and that would break the code
ttm = (timeDiff(t1, "23:59:59") + 1)
taf = (timeDiff("00:00:00", t2))
d = (ttm + taf)
}
return (d)
}
######## TEST CODE ########
t1 = "23:30:45"
t2 = "03:12:00"
d <- timeDiff(t1, t2)
# convert seconds to whole hours
hh = as.integer(d / (60 * 60))
# find the remaining seconds
r = (d - (hh * (60 * 60)))
# convert seconds to whole minutes
mm = as.integer(r / 60)
# find the remaining seconds (using the mod operator this time)
ss = (r - (mm * 60))
# format the required output
out <- paste(hh, "HOURS", mm, "MINUTES", ss, "SECONDS")
print(out)
## [1] "3 HOURS 41 MINUTES 15 SECONDS"
How would you solve the problem without the use of recursion? Is that solution more elegant? Easier to understand?
References
No references.
LS0tCnRpdGxlOiAiRmlyc3QgU3RlcHMgaW4gUiIKcGFyYW1zOgogIGNhdGVnb3J5OiA2CiAgbnVtYmVyOiAxMDEKICB0aW1lOiA0NQogIGxldmVsOiBiZWdpbm5lcgogIHRhZ3M6ICJyLHByaW1lciIKICBkZXNjcmlwdGlvbjogIkludHJvZHVjZXMgdGhlIGtleSBwcm9ncmFtbWluZyBtZWNoYW5pc21zIG9mIFIuIFNob3dzIGhvdyB0byB3b3JrIHdpdGgKICAgICAgICAgICAgICAgIGNvbnRyb2wgc3RydWN0dXJlcywgdmFyaWFibGVzLCBmdW5jdGlvbnMsIGFuZCBwYWNrYWdlcy4gTG9hZHMgZGF0YQogICAgICAgICAgICAgICAgZnJvbSBDU1YgZmlsZXMgaW50byBkYXRhIGZyYW1lcy4gQ29ubmVjdHMgdG8gU1FMIGRhdGFiYXNlcy4iCmRhdGU6ICI8c21hbGw+YHIgU3lzLkRhdGUoKWA8L3NtYWxsPiIKYXV0aG9yOiAiPHNtYWxsPk1hcnRpbiBTY2hlZGxiYXVlcjwvc21hbGw+IgplbWFpbDogIm0uc2NoZWRsYmF1ZXJAbmV1LmVkdSIKYWZmaWxpdGF0aW9uOiAiTm9ydGhlYXN0ZXJuIFVuaXZlcnNpdHkiCm91dHB1dDogCiAgYm9va2Rvd246Omh0bWxfZG9jdW1lbnQyOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGNvbGxhcHNlZDogZmFsc2UKICAgIG51bWJlcl9zZWN0aW9uczogZmFsc2UKICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgIHRoZW1lOiBzcGFjZWxhYgogICAgaGlnaGxpZ2h0OiB0YW5nbwotLS0KCi0tLQp0aXRsZTogIjxzbWFsbD5gciBwYXJhbXMkY2F0ZWdvcnlgLmByIHBhcmFtcyRudW1iZXJgPC9zbWFsbD48YnIvPjxzcGFuIHN0eWxlPSdjb2xvcjogIzJFNDA1MzsgZm9udC1zaXplOiAwLjllbSc+YHIgcm1hcmtkb3duOjptZXRhZGF0YSR0aXRsZWA8L3NwYW4+IgotLS0KCmBgYHtyIGNvZGU9eGZ1bjo6cmVhZF91dGY4KHBhc3RlMChoZXJlOjpoZXJlKCksJy9SL19pbnNlcnQyREIuUicpKSwgaW5jbHVkZSA9IEZBTFNFfQpgYGAKCiMjIFByZWZhY2UKClRoaXMgdHV0b3JpYWwgcHJlc3VtZXMgdGhhdCB5b3UgaGF2ZSBSLCBSIFN0dWRpbywgYW5kIFNRTGl0ZSBpbnN0YWxsZWQsIGFsdGhvdWdoIHRvIGJlIHRlY2huaWNhbGx5IGFjY3VyYXRlLCB5b3UgZG8gYWN0dWFsbHkgbmVlZCB0byBoYXZlIFNRTGl0ZSBpbnN0YWxsZWQgaWYgeW91IGFyZSBjb25uZWN0ZWQgZnJvbSBSIGFzIHRoZSBSU1FMaXRlIHBhY2thZ2UgY29udGFpbnMgYWxsIG5lY2Vzc2FyeSBjb2RlIHRvIG9wZW4gYSBTUUxpdGUgZGF0YWJhc2UgZmlsZS4KCkZvbGxvdyB0aGUgdHV0b3JpYWwgYnkgc3RhcnRpbmcgeW91ciBvd24gUiBOb3RlYm9vayBpbiBSIFN0dWRpby4gSWYgeW91IGRvIG5vdCBhbHJlYWR5IGhhdmUgUiBhbmQvb3IgUiBTdHVkaW8geW91IHdpbGwgbmVlZCB0byBkb3dubG9hZCBhbmQgaW5zdGFsbCB0aGVtLiBZb3UgbXVzdCBmaXJzdCBpbnN0YWxsIFIgZnJvbSBbUiBQcm9qZWN0XShodHRwczovL2Nsb3VkLnItcHJvamVjdC5vcmcvKSBhbmQgdGhlbiB0aGUgUiBTdHVkaW8gSURFIGZyb20gW1IgU3R1ZGlvXShodHRwczovL3JzdHVkaW8uY29tL3Byb2R1Y3RzL3JzdHVkaW8vZG93bmxvYWQvKS4gQWx0ZXJuYXRpdmVseSwgcmF0aGVyIHRoYW4gaW5zdGFsbGluZyBSIGFuZCBSIFN0dWRpbyBsb2NhbGx5LCB5b3UgY2FuIGRvIHRoZSB0dXRvcmlhbCB1c2luZyBbUiBTdHVkaW8gQ2xvdWRdKGh0dHBzOi8vcnN0dWRpby5jbG91ZC8pLgoKIyMgSW50cm9kdWN0aW9uCgpUaGlzIGlzIGFuIFtSIE1hcmtkb3duXShodHRwOi8vcm1hcmtkb3duLnJzdHVkaW8uY29tKSBOb3RlYm9vay4gV2hlbiB5b3UgZXhlY3V0ZSBjb2RlIHdpdGhpbiB0aGUgbm90ZWJvb2ssIHRoZSByZXN1bHRzIGFwcGVhciBiZW5lYXRoIHRoZSBjb2RlLiBJdCBkZW1vbnN0cmF0ZXMgaG93IHRvIHdvcmsgd2l0aCBkYXRhIGZyYW1lcywgb25lIG9mIHRoZSBtb3N0IGltcG9ydGFudCBSIGRhdGEgdHlwZXMgZm9yIGRhdGEgcHJvY2Vzc2luZyBpbiBhZGRpdGlvbiB0byB2ZWN0b3IgYW5kIHNjYWxhcnMuCgpUaGUgdHV0b3JpYWwgaXMgZ2VhcmVkIHRvd2FyZHMgc3R1ZGVudHMgaW4gaW5mb3JtYXRpb24gc2NpZW5jZSwgZGF0YSBzY2llbmNlLCBhbmQgZGF0YWJhc2UgZGVzaWduLiBJdCBkZW1vbnN0cmF0ZXMgYmFzaWMgc3ludGF4IGluIFIgdGhhdCBhcmUgbW9zdCBvZnRlbiB1c2VkIGZvciBkYXRhIHByb2Nlc3NpbmcgcmF0aGVyIHRoYW4gc3RhdGlzdGljcy4KCkV4ZWN1dGUgY2h1bmtzIGJ5IGNsaWNraW5nIHRoZSAqUnVuKiBidXR0b24gd2l0aGluIHRoZSBjaHVuayBvciBieSBwbGFjaW5nIHlvdXIgY3Vyc29yIGluc2lkZSBpdCBhbmQgcHJlc3NpbmcgKkN0cmwrU2hpZnQrRW50ZXIqLiBUaGUgY29kZSBydW5zIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGUgY2h1bmtzIGFyZSBleGVjdXRlZCwgc28gbm9uLWxpbmVhciBjb2RlIGV4ZWN1dGlvbiBpcyBwb3NzaWJsZSB1bmxlc3MgeW91IGluc3RydWN0IFIgU3R1ZGlvIHRvIHJ1biBhbGwgY2h1bmtzIHN0YXJ0aW5nIGF0IHRoZSBmaXJzdCBjaHVuay4KCkFkZCBhIG5ldyBjaHVuayBieSBjbGlja2luZyB0aGUgKkluc2VydCBDaHVuayogYnV0dG9uIG9uIHRoZSB0b29sYmFyIG9yIGJ5IHByZXNzaW5nICpDdHJsK0FsdCtJKi4KCldoZW4geW91IHNhdmUgdGhlIG5vdGVib29rLCBhbiBIVE1MIGZpbGUgY29udGFpbmluZyB0aGUgY29kZSBhbmQgb3V0cHV0IHdpbGwgYmUgc2F2ZWQgYWxvbmdzaWRlIGl0IChjbGljayB0aGUgKlByZXZpZXcqIGJ1dHRvbiBvciBwcmVzcyAqQ3RybCtTaGlmdCtLKiB0byBwcmV2aWV3IHRoZSBIVE1MIGZpbGUpLgoKVGhlIHByZXZpZXcgc2hvd3MgeW91IGEgcmVuZGVyZWQgSFRNTCBjb3B5IG9mIHRoZSBjb250ZW50cyBvZiB0aGUgZWRpdG9yLiBDb25zZXF1ZW50bHksIHVubGlrZSAqS25pdCosICpQcmV2aWV3KiBkb2VzIG5vdCBydW4gYW55IFIgY29kZSBjaHVua3MuIEluc3RlYWQsIHRoZSBvdXRwdXQgb2YgdGhlIGNodW5rIHdoZW4gaXQgd2FzIGxhc3QgcnVuIGluIHRoZSBlZGl0b3IgaXMgZGlzcGxheWVkLgoKIyMgV29ya2luZyBpbiBSCgpUbyB3cml0ZSAicHJvZ3JhbXMiIGluIFIgeW91IHdpbGwgbmVlZCBCYXNlIFIgd2hpY2ggeW91IGNhbiBkb3dubG9hZCBmb3IgTGludXgsIE1hY09TLCBhbmQgV2luZG93cyBmcm9tIFtSIFByb2plY3RdKGh0dHBzOi8vd3d3LnItcHJvamVjdC5vcmcvKS4gVGhpcyBpcyB0aGUgY29yZSBsYW5ndWFnZSB3aXRoIGFuIGludGVyYWN0aXZlIGNvbnNvbGUuIFByb2dyYW1zLCBvciBtb3JlIGFwdGx5IFIgc2NyaXB0cywgY2FuIGJlIGJ1aWx0IGluIGFueSB0ZXh0IGVkaXRvciAoVGV4dEVkaXQsIE5vdGVwYWQsIHZpLCBTdWJsaW1lLCBKRWRpdCwgZXRjLikuCgpSIGRvZXNuJ3QgcmVhbGx5IGhhdmUgInByb2dyYW1zIiBpbiB0aGUgdHJhZGl0aW9uYWwgc2Vuc2UuIFRoZXJlIGlzIG5vICJjb21waWxpbmciOyBwcm9ncmFtcyBhcmUgInNjcmlwdHMiIHRoYXQgYXJlIGludGVycHJldGVkLiBJdCBpcyBwb3NzaWJsZSB0byBleGVjdXRlIFIgc2NyaXB0cyBmcm9tIHRoZSBjb21tYW5kIGxpbmUgYW5kIHRodXMgaGF2ZSB0aGVtIGJlaGF2ZSBsaWtlIHByb2dyYW1zIGJ1dCBtb3N0IHdvcmsgaXMgZG9uZSBpbiBSIE5vdGVib29rcyB0aGF0IGFyZSBjaHVua3Mgb2YgY29kZS4KCk1vc3QgcHJvZ3JhbW1pbmcgaXMgZG9uZSB3aXRoIGFuIElERSAoSW50ZWdyYXRlZCBEZXZlbG9wbWVudCBFbnZpcm9ubWVudCkuIFRoZSBtb3N0IGNvbW1vbiBpcyBSIFN0dWRpbyBkb3dubG9hZGFibGUgZnJvbSBbUlN0dWRpb10oaHR0cHM6Ly93d3cucnN0dWRpby5jb20vcHJvZHVjdHMvcnN0dWRpby9kb3dubG9hZC8pLiBUaGVyZSBob3N0ZWQgdmVyc2lvbiBvZiBSIFN0dWRpbyBhdmFpbGFibGUgYXQgW3JzdHVkaW8uY2xvdWRdKGh0dHA6Ly9yc3R1ZGlvLmNsb3VkKS4KClRoZSB0dXRvcmlhbCBiZWxvdyBleHBsYWlucyBob3cgdG8gZ2V0IHN0YXJ0ZWQgd2l0aCBSIE5vdGVib29rczoKCjxpZnJhbWUgc3R5bGU9ImJvcmRlcjogMXB4IHNvbGlkICM0NjQ2NDY7IiBzcmM9Imh0dHBzOi8vbm9ydGhlYXN0ZXJuLmhvc3RlZC5wYW5vcHRvLmNvbS9QYW5vcHRvL1BhZ2VzL0VtYmVkLmFzcHg/aWQ9ODBjMmNmMDItMDBkMi00MjdjLThmY2QtYWJlMDAwZjA2ZjBkJmFtcDthdXRvcGxheT1mYWxzZSZhbXA7b2ZmZXJ2aWV3ZXI9dHJ1ZSZhbXA7c2hvd3RpdGxlPWZhbHNlJmFtcDtzaG93YnJhbmQ9ZmFsc2UmYW1wO3N0YXJ0PTAmYW1wO2ludGVyYWN0aXZpdHk9YWxsIiB3aWR0aD0iMzIwIiBoZWlnaHQ9IjE4MCIgYWxsb3dmdWxsc2NyZWVuPSJhbGxvd2Z1bGxzY3JlZW4iIGFsbG93PSJhdXRvcGxheSIgZGF0YS1leHRlcm5hbD0iMSI+Cgo8L2lmcmFtZT4KCiMjIEJhc2ljIFIKClIgaXMgYSBzY3JpcHRlZCBsYW5ndWFnZSB3aGljaCBtZWFucyB0aGF0IHlvdSBkbyBub3QgbmVlZCB0byBjb21waWxlIHRoZSBwcm9ncmFtIGJlZm9yZSBydW5uaW5nIGl0LiBTdGF0ZW1lbnRzIGFuZCBleHByZXNzaW9ucyBhcmUgZXhlY3V0ZWQgYXMgeW91IHR5cGUgdGhlbS4KCiMjIFIgQ29kZSBDaHVua3MKCldlIHdpbGwgb25seSBkaXNjdXNzIGhvdyB0byB3cml0ZSBSICJwcm9ncmFtcyIgdXNpbmcgYW4gUiBOb3RlYm9vayBpbiBSIFN0dWRpby4gUHJvZ3JhbXMgaW4gUiBydW4gZnJvbSBzdGFydCB0byBlbmQuIEVhY2ggY2h1bmsgc2hvdWxkIGJlIGEgc3RlcCBpbiB5b3VyIGFuYWx5c2lzIG9yIGRhdGEgcHJvamVjdC4gTmFtZSB5b3VyIGNvZGUgY2h1bmssIHNvIHlvdSBjYW4gcXVpY2tseSBuYXZpZ2F0ZSB0byB0aGVtLgoKSW4gdGhlIGNodW5rIGJlbG93LCB0aGUgdmFyaWFibGUgKmNhcnMqIHBhc3NlZCB0byB0aGUgYnVpbHQtaW4gQmFzZSBSIGZ1bmN0aW9uIDxjb2RlPnBsb3Q8L2NvZGU+IGlzIG9uZSBvZiB0aGUgZG96ZW5zIG9mICJidWlsdC1pbiIgZGF0YSBmcmFtZXM7IGEgZGF0YSBmcmFtZSBiZWluZyBkYXRhIGFycmFuZ2VkIGluIHJvd3MgYW5kIGNvbHVtbnMgc2ltaWxhciB0byBhIHNwcmVhZHNoZWV0IG9yIENTViBmaWxlLgoKTm90ZSB0aGF0IHlvdSBjYWxsIGEgZnVuY3Rpb24gYnkgdXNpbmcgdGhlIGZ1bmN0aW9uJ3MgbmFtZSBmb2xsb3dlZCBieSB0aGUgYXJndW1lbnRzIHlvdSB3aXNoIHRvIHBhc3MgdG8gdGhlIGZ1bmN0aW9uLiBPZiBjb3Vyc2UsIHlvdSBuZWVkIHRvIGZvbGxvdyB0aGUgZGVmaW5pdGlvbiBvZiB0aGUgZnVuY3Rpb24uIE1hbnkgZnVuY3Rpb25zIGFyZSBzaW1wbHkgImJ1aWx0LWluIiB3aGlsZSBvdGhlcnMgY29tZSBmcm9tIHBhY2thZ2VzIHRoYXQgeW91IG5lZWQgdG8gZXhwbGljaXRseSBsb2FkIGludG8geW91ciBwcm9ncmFtLgoKTm90ZSB0aGF0IHRoZXJlIGlzIG5vIHNlbWljb2xvbiBhdCB0aGUgZW5kIG9mIGEgbGluZS4KCjxjb2RlPiBcYFxgXGB7ciBuYW1lZENodW5rLCBldmFsPUZBTFNFfTxici8+IHBsb3QoeCA9IG10Y2Fyc1wkbXBnLCB5ID0gbXRjYXJzXCRocCk8YnIvPiBcYFxgXGAgPC9jb2RlPgoKIyMjIEV4cHJlc3Npb25zCgpSIGNhbiBiZSBkaXJlY3RseSB1c2VkIHRvIHNvbHZlIHNpbXBsZSBvciBjb21wbGV4IG1hdGhlbWF0aWNhbCBleHByZXNzaW9ucy4KCmBgYHtyfQojIFsxXSBpbiB0aGUgYWJvdmUgYW5zd2VyIGluZGljYXRlcyB0aGUgaW5kZXggb2YgeW91ciByZXN1bHRzLgojIFIgYWx3YXlzIHNob3dzIHRoZSByZXN1bHQgd2l0aCBpbmRleCBmb3IgZWFjaCByb3cuCgooKDJeMykqNSktMQpgYGAKCmBgYHtyfQojIHNxcnQgYW5kIGV4cCBhcmUgYnVpbHQtaW4gZnVuY3Rpb25zIGluIFIgZm9yIGZpbmRpbmcgU3F1YXJlIHJvb3QgYW5kIGV4cG9uZW50aWFsIHJlc3BlY3RpdmVseS4KCnNxcnQoNCkqIGV4cCgyKQpgYGAKCiMjIyBWYXJpYWJsZXMgYW5kIElkZW50aWZpZXJzCgpIb2xkaW5nIGEgdmFsdWUgaW4gYSB2YXJpYWJsZSBpcyBkb25lIHRocm91Z2ggYXNzaWdubWVudC4gT25jZSB5b3UgYXNzaWduIGEgdmFsdWUgdG8gYSB2YXJpYWJsZSwgdGhlIHZhcmlhYmxlcyBiZWNvbWVzIGFuIFIgb2JqZWN0LiBUaGVyZSBhcmUgdHdvIHdheXMgdG8gZG8gYW4gYXNzaWdubWVudCwgdXNpbmcgJz0nIG9yIHdpdGggJ1w8LScuIFRoZSBsYXR0ZXIgaXMgdGhlIHByZWZlcnJlZCB3YXkgaW4gUiBidXQgdGhlIGZvcm1lciBtaWdodCBiZSBtb3JlIGZhbWlsaWFyIHRvIHRob3NlIHByb2dyYW1tZXJzIGNvbWluZyB0byBSIGZyb20gSmF2YSwgQysrLCBvciBQeXRob24uCgpOb3RlIHRoYXQgdmFyaWFibGVzIGFyZSBleHBsaWNpdGx5IGRlZmluZWQgb3IgZGVjbGFyZWQuIFRoZSBmaXJzdCB0aW1lIGEgdmFyaWFibGUgaXMgYXNzaWduZWQgYSB2YWx1ZSBkZWZpbmVzIHRoZSB2YXJpYWJsZSBhbmQgaXRzIHR5cGUuIFRoZSB0eXBlIGlzIGJhc2VkIG9uIHRoZSB2YWx1ZSB0aGF0IGlzIGFzc2lnbmVkLiBVbmxpa2Ugb3RoZXIgcHJvZ3JhbW1pbmcgbGFuZ3VhZ2VzIHN1Y2ggYXMgQysrLCBDIywgb3IgSmF2YSwgUiBpcyBub3Qgc3Ryb25nbHkgdHlwZWQ6IHRoZSB0eXBlIG9mIGEgdmFyaWFibGUgY2FuIGNoYW5nZSB3aGVuIGEgdmFsdWUgb2YgYSBkaWZmZXJlbnQgdHlwZSBpcyBhc3NpZ25lZC4gQSB2YXJpYWJsZSBjYW4gYmUgdXNlZCBpbiBhbiBleHByZXNzaW9uLiBJdHMgdmFsdWUgY2FuIGJlIGluc3BlY3RlZCBieSBqdXN0IHVzaW5nIHRoZSB2YXJpYWJsZSBieSBpdHNlbGYuCgpUaGUgdmFsdWUgb2YgYSB2YXJpYWJsZSBjYW4gYmUgZGlzcGxheWVkIGVpdGhlciBieSB1c2luZyB0aGUgdmFyaWFibGUgYnkgaXRzZWxmIG9yIHVzaW5nIHRoZSA8Y29kZT5wcmludCgpPC9jb2RlPiBmdW5jdGlvbi4KCmBgYHtyfQojIGFzc2lnbm1lbnQgd2l0aCAnPScgb2YgYSBudW1iZXIKeCA9IDEyCiMgaW5zcGVjdCAocHJpbnQvZGlzcGxheSkgdGhlIHZhbHVlCngKCiMgYXNzaWdubWVudCBhIG5ldyB2YWx1ZSBhbmQgY2hhbmdlIGl0cyB0eXBlIHRvICJ0ZXh0Igp4ID0gIkhlbGxvIgp4CgojIGFzc2lnbm1lbnQgd2l0aCAnPC0nCnggPC0gMTIKcHJpbnQoeCkKYGBgCgpUaGUgcnVsZXMgZm9yIG5hbWluZyBhbiBpZGVudGlmaWVyICh2YXJpYWJsZSwgZnVuY3Rpb24sIG9yIHBhY2thZ2UgbmFtZSkgZm9yIGFuIG9iamVjdCBhcmUgYXMgZm9sbG93czoKCmlkZW50aWZpZXJzIGFyZSBjYXNlLXNlbnNpdGl2ZSBhbmQgY2Fubm90IGNvbnRhaW4gc3BhY2VzIG9yIHNwZWNpYWwgY2hhcmFjdGVycyBzdWNoIGFzICMsICUsIFwkLCBcQCwgXCosICYsIFxeLCAhLCBcfiBhbiBpZGVudGlmaWVyIG11c3Qgc3RhcnQgd2l0aCBhIGxldHRlciwgYnV0IG1heSBjb250YWluIGFueSBjb21iaW5hdGlvbiBvZiBsZXR0ZXJzIGFuZCBkaWdpdHMgdGhlcmVhZnRlciBzcGVjaWFsIGNoYXJhY3RlcnMgZG90ICguKSBhbmQgdW5kZXJzY29yZSAoXF8pIGFyZSBhbGxvd2VkCgpUaGUgZG90ICguKSBpcyBhIHJlZ3VsYXIgY2hhcmFjdGVyIGluIFIgYW5kIHRoYXQgY2FuIGJlIGNvbmZ1c2luZyBhcyBvdGhlciBsYW5ndWFnZSAoKmUuZy4qLCBKYXZhKSB1c2UgZG90IHRvIGRlc2lnbmF0ZSBwcm9wZXJ0eSBvciBtZXRob2QgYWNjZXNzLCAqZS5nKiwgaW4gSmF2YSAqeC52YWwqIG1lYW5zIHRoYXQgeW91IGFyZSBhY2Nlc3NpbmcgdGhlICp2YWwqIHByb3BlcnR5IG9mIHRoZSBvYmplY3QgKngqLgoKU29tZSBleGFtcGxlcyBvZiBsZWdhbCB2YXJpYWJsZSBuYW1lcyBhcmU6IGRmLCBkZjIsIGRmLnR4bnMsIGRmX2FsbDIwMTcuIFRoZXNlIGFyZSBzb21lIGlsbGVnYWwgdmFyaWFibGUgbmFtZXM6ICoyZGYqIChjYW5ub3Qgc3RhcnQgd2l0aCBhIGRpZ2l0KSwgKnJzXCRhbGwqIChjYW5ub3QgY29udGFpbiBhIFwkOyB0aGUgXCQgaXMgdXNlZCB0byBhY2Nlc3MgY29sdW1ucyBpbiBhIGRhdGFmcmFtZSksICpycyMqIChvbmx5IC4gYW5kIFxfIGFyZSBhbGxvd2VkIGluIGFkZGl0aW9uIHRvIGRpZ2l0cyBhbmQgbGV0dGVycykuCgpJdCBpcyBjb25zaWRlcmVkIGdvb2QgcHJvZ3JhbW1pbmcgcHJhY3RpY2UgdG8gZ2l2ZSBpZGVudGlmaWVycyBhIHNlbnNpYmxlIG5hbWUgdGhhdCBoaW50cyBhcyB0byB3aGF0IGlzIHN0b3JlZCBpbiB0aGUgdmFyaWFibGUgcmF0aGVyIHRoYW4gdXNpbmcgcmFuZG9tIG5hbWUgbGlrZSB4LCB2YWwsIG9yIGkzMy4gSWRlbnRpZmllcnMgc2hvdWxkIGJlIG5hbWVkIGNvbnNpc3RlbnRseS4gTWFueSBwcm9ncmFtbWVycyB1c2Ugb25lIG9mIHR3byBzdHlsZXM6CgotICAgdW5kZXJzY29yZXMsICplLmcuKiwgKmludGVyZXN0X3JhdGUqCi0gICBjYW1lbENhc2UsICplLmcuKiwgKnNxdWFyZVJvb3QqLCAqZ3JhcGhEYXRhKiwgKmN1cnJlbnRXb3JraW5nRGlyZWN0b3J5KgoKTm90ZSB0aGF0IFIgaXMgY2FzZSBzZW5zaXRpdmUgd2hpY2ggbWVhbnMgdGhhdCBSIHRyZWF0cyB0aGUgaWRlbnRpZmllcnMgKkFQKiBhbmQgKmFwKiBhcyBkaWZmZXJlbnQgb2JqZWN0cy4gQXMgYSBzaWRlIG5vdGUsIGZpbGVzIG1heSBhbHNvIGJlIGNhc2Ugc2Vuc2l0aXZlIGJ1dCB0aGF0IGRlcGVuZHMgb24gdGhlIG9wZXJhdGluZyBzeXN0ZW0uIE1hY09TIGFuZCBMaW51eCBhcmUgY2FzZSBzZW5zaXRpdmUsIHdoaWxlIFdpbmRvd3MgaXMgY2FzZSBhd2FyZSBidXQgbm90IGNhc2Ugc2Vuc2l0aXZlLiBGb3IgZXhhbXBsZSwgb24gTWFjT1MgYW5kIExpbnV4IHRoZXJlIGlzIGEgZGlmZmVyZW5jZSBiZXR3ZWVuICJBaXJQYXNzZW5nZXJzLnR4dCIgYW5kICJhaXJwYXNzZW5nZXJzLnR4dCIgd2hpbGUgb24gV2luZG93cyB0aGVyZSBpcyBub3QuIFNRTCBpcyBhbHNvIG5vdCBjYXNlIHNlbnNpdGl2ZS4gSXQgaXMgYSBiZXN0IHByYWN0aWNlIHRvIGFzc3VtZSBjYXNlIHNlbnNpdGl2aXR5LgoKIyMgQnVpbHQtaW4gRGF0YSBGcmFtZXMKClRoZXJlIGFyZSBudW1lcm91cyBkYXRhIGZyYW1lcyBidWlsdCBpbnRvIFIgdGhhdCBhcmUgYWNjZXNzaWJsZSB3aXRob3V0IGxvYWRpbmcgdGhlbSBmaXJzdCBmcm9tIGV4dGVybmFsIGZpbGVzLiBUaGVzZSBkYXRhIGZyYW1lcyBhcmUgZm9yIGV4cGVyaW1lbnRhdGlvbiBhbmQgbGVhcm5pbmcgYW5kIG5vdCBmb3IgYWN0dWFsIGFuYWx5dGljcyB3b3JrLiBPbmUgc3VjaCBidWlsdC1pbiBkYXRhIGZyYW1lIGlzIDxjb2RlPm10Y2FyczwvY29kZT4uIFRvIGdldCBhIGxpc3Qgb2YgYWxsIGJ1aWx0LWluIGRhdGEgZnJhbWVzLCBydW4gPGNvZGU+ZGF0YSgpPC9jb2RlPi4KCmBgYHtyfQptdGNhcnMKYGBgCgo8Y29kZT5tdGNhcnM8L2NvZGU+IGFuZCA8Y29kZT5tdGNhcnM8L2NvZGU+IHByaW50IG91dCB0aGUgZmlyc3QgYW5kIGxhc3Qgc2l4IHJvd3Mgb2YgYSBkYXRhIGZyYW1lLCByZXNwZWN0aXZlbHkuIFlvdSBjYW4gc3BlY2lmeSB0aGUgbnVtYmVyIG9mIHJvd3MgdG8gZGlzcGxheS4KCmBgYHtyfQpoZWFkKG10Y2FycykKdGFpbChtdGNhcnMpCgpoZWFkKG10Y2FycywgMykKYGBgCgojIyBBY2Nlc3NpbmcgUm93cywgQ29sdW1ucywgYW5kIEVsZW1lbnRzIChDZWxscykgb2YgYSBEYXRhIEZyYW1lCgpEYXRhIGZyYW1lcyBhcmUgdmVyeSBzaW1pbGFyIHRvIHRhYmxlcyBpbiByZWxhdGlvbmFsIGRhdGFiYXNlcyBhbmQgc3ByZWFkc2hlZXRzLiBUaGV5IGhhdmUgcm93cyBhbmQgY29sdW1ucyBhbmQgdGhlIGludGVyc2VjdGlvbiBvZiBhIHJvdyBhbmQgY29sdW1uIGlzIGEgY2VsbCAob3IgZWxlbWVudCkuIFRoZSBvcmRlciBvZiBhY2Nlc3MgaXMgcm93IGZvbGxvd2VkIGJ5IGNvbHVtbiwgZS5nLCB0aGUgdGhpcmQgZWxlbWVudCBpbiB0aGUgZm91cnRoIHJvdyBvZiB0aGUgZGF0YSBmcmFtZSA8Y29kZT5tdGNhcnM8L2NvZGU+IGlzIDxjb2RlPm10Y2Fyc1s0LDNdPC9jb2RlPi4gTm90ZSB0aGF0IHRoaXMgaXMgcmV2ZXJzZWQgZnJvbSB0aGUgd2F5IEV4Y2VsIGFuZCBvdGhlciBzcHJlYWRzaGVldHMgd29yay4gVGhlIDxjb2RlPlw8LTwvY29kZT4gaXMgdGhlIG9wZXJhdG9yIGZvciBhc3NpZ25tZW50LCBhbHRob3VnaCA8Y29kZT49PC9jb2RlPiBhbHNvIHdvcmtzLiBXZSB3aWxsIHNlZSBhbmQgdXNlIGJvdGguCgpUbyBkaXNwbGF5IGEgdmFsdWUsIGVpdGhlciB1c2UgdGhlIDxjb2RlPnByaW50PC9jb2RlPiBmdW5jdGlvbiBvciBqdXN0IHVzZSB0aGUgdmFyaWFibGUgYnkgaXRzZWxmLiBUbyBwcmludCBtdWx0aXBsZSBpdGVtcywgdXNlIHRoZSA8Y29kZT5wYXN0ZTA8L2NvZGU+IGZ1bmN0aW9uLgoKYGBge3J9CnYgPC0gbXRjYXJzWzQsM10KeCA9IG10Y2Fyc1s0LDNdCgpwcmludChwYXN0ZTAoInYgPSAiLHYsIiBhbmQgeCA9ICIseCkpCmBgYAoKTGVhdmluZyBvdXQgYSBkaW1lbnNpb24gKHJvdyBvciBjb2x1bW4pIGFjY2Vzc2VzIHRoZSBlbnRpcmUgcm93IG9yIGNvbHVtbi4gVGhlIHJlc3VsdGFudCBpcyBhIGRhdGEgZnJhbWUgd2l0aCBhIHNpbmdsZSByb3cuIE9mdGVuIHRoZSB2YWx1ZXMgbXVzdCBiZSBjb252ZXJ0ZWQgdG8gYSB2ZWN0b3IgZGF0YSB0eXBlLiBDb252ZXJzaW9ucyBvZiB2YXJpYWJsZXMgZnJvbSBvbmUgdHlwZSB0byBhbm90aGVyIGlzIGRvbmUgd2l0aCB0aGUgZmFtaWx5IG9mIDxjb2RlPmFzLnh4eHg8L2NvZGU+IGZ1bmN0aW9ucywgKmUuZy4qLCA8Y29kZT5hcy52ZWN0b3I8L2NvZGU+LCA8Y29kZT5hcy5udW1lcmljPC9jb2RlPiwgb3IgPGNvZGU+YXMuZmFjdG9yPC9jb2RlPi4gVmVjdG9ycyBjYW4gY29udGFpbiBudW1lcmljIG9yIGNoYXJhY3RlciBkYXRhIGJ1dCBhbGwgZWxlbWVudHMgbXVzdCBiZSBvZiB0aGUgc2FtZSB0eXBlLiBJbiBSLCBhIGxpc3QgaXMgc2ltaWxhciB0byBhIHZlY3RvciBidXQgaXQgbWF5IGNvbnRhaW4gYSBtaXggb2YgZWxlbWVudHMuIEEgbWF0cml4IGlzIHNpbWlsYXIgdG8gYSBkYXRhIGZyYW1lIGJ1dCBpdCBjYW4gb25seSBjb250YWluIG51bWJlcnMgYW5kIGl0IGNhbiBoYXZlIG1vcmUgdGhhbiB0d28gZGltZW5zaW9ucy4KClNvbWUgZnVuY3Rpb25zIGV4cGVjdCBkYXRhIGZyYW1lcywgc29tZSB2ZWN0b3JzLCBzb21lIGxpc3RzLiBZb3UgbmVlZCB0byByZWFkIHRoZSBkb2N1bWVudGF0aW9uIG9mIGEgZnVuY3Rpb24gdG8gZmluZCBvdXQuIEZ1cnRoZXJtb3JlLCBzb21lIGZ1bmN0aW9ucyB3aWxsIGF1dG9tYXRpY2FsbHkgY29udmVydCAoYWxzbyBjYWxsZWQgY29lcmNlKSBhIHZhcmlhYmxlIGZyb20gb25lIHR5cGUgdG8gdGhlIG9uZSBpdCByZXF1aXJlcy4KCllvdSBjYW4gYWxzbyBhY2Nlc3MgYSBjb2x1bW4gaW4gZGF0YSBmcmFtZSBieSBpdHMgY29sdW1uIG5hbWUuIEZvciBhbiBlbnRpcmUgY29sdW1uIHlvdSBlaXRoZXIgdXNlIHRoZSBjb2x1bW5zIHBvc2l0aW9uIG9yIGl0cyBuYW1lOiA8Y29kZT5kZlssY29sdW1uXTwvY29kZT4gb3IgPGNvZGU+ZGZcJGNvbHVtbk5hbWU8L2NvZGU+LgoKYGBge3J9CiMgYWxsIG9mIHJvdyA0OyB0aGUgcmVzdWx0IGlzIGEgZGF0YSBmcmFtZQpyIDwtIG10Y2Fyc1s0LF0Kc3VtKHIpCgpjIDwtIG10Y2Fyc1szLF0KY1sxLDNdCgptdGNhcnNbYygxLDQpXSAgICMgY29sdW1ucyAxIGFuZCA0IGFzIGEgbmV3IGRhdGFmcmFtZQoKbXRjYXJzWywyXSAgICAgICAjIGFsbCBvZiBjb2x1bW4gMgptdGNhcnNbNTo3LF0gICAgICMgcm93cyA1IHRvIDcgYXMgYSBuZXcgZGF0YWZyYW1lCm10Y2FycyRjeWwgICAgICAgIyBjb2x1bW4gbmFtZWQgImN5bCIKbXRjYXJzJGN5bFsyXSAgICAjIDJuZCByb3cgaW4gdGhlIGNvbHVtbiAiY3lsIgoKbXRjYXJzJGN5bFszOjldICAjIHJvd3MgMyB0byA5IGZvciBjb2x1bW4gImN5bCIgYXMgYSB2ZWN0b3IKCncgPC0gbXRjYXJzJG1wZwptZWFuKHcpCmBgYAoKIyMgQWdncmVnYXRpb24gYW5kIFN0YXRpc3RpY2FsIEZ1bmN0aW9ucwoKQXMgYSBsYW5ndWFnZSB3aXRoIGl0cyBvcmlnaW4gaW4gc3RhdGlzdGljcyBhbmQgc3RhdGlzdGljYWwgZGF0YSBwcm9jZXNzaW5nLCBSIGhhcyBhIHBsZXRob3JhIG9mIHN0YXRpc3RpY2FsIGZ1bmN0aW9ucy4gU29tZSBvZiB0aGUgbW9zdCBpbXBvcnRhbnQgZnVuY3Rpb25zIGZvciBkYXRhIHByb2Nlc3NpbmcgYXJlIHNob3duIGJlbG93LiBDb25zdWx0IG9ubGluZSBkb2N1bWVudGF0aW9uIGFuZCBzdGF0aXN0aWNzIHJlZmVyZW5jZXMgZm9yIG1vcmUgaW5mb3JtYXRpb24sICplLmcuKiwgW0hvdyBUbyBHZXQgRGVzY3JpcHRpdmUgU3RhdGlzdGljcyBJbiBSXShodHRwczovL3d3dy5wcm9ncmFtbWluZ3IuY29tL3N0YXRpc3RpY3MvZGVzY3JpcHRpdmUtc3RhdGlzdGljcy1pbi1yLyM6fjp0ZXh0PVRoZSUyMHN1bW1hcnklMjBmdW5jdGlvbiUyMGluJTIwUiUyMGlzJTIwb25lJTIwb2Ysc3VjaCUyMGFzJTIwcmFuZ2UlMkMlMjBtZWFuJTJDJTIwbWVkaWFuJTIwYW5kJTIwaW50ZXJwZXJjZW50aWxlJTIwcmFuZ2VzKSBhbmQgW0Jhc2UgUiBTdGF0aXN0aWNhbCBGdW5jdGlvbnNdKGh0dHBzOi8vd3d3LmR1bW1pZXMuY29tL2VkdWNhdGlvbi9tYXRoL3N0YXRpc3RpY3MvYmFzZS1yLXN0YXRpc3RpY2FsLWZ1bmN0aW9ucy8pLgoKYGBge3J9CiMgaW1wb3J0IGRhdGEgZm9yIGRlc2NyaXB0aXZlIHN0YXRpc3RpY3MsIHRoZSBidWlsdC1pbiBkYXRhIGZyYW1lICd3YXJwYnJlYWtzJwpkYXRhKHdhcnBicmVha3MpCgojIHN1bW1hcnkgZGVzY3JpcHRpdmUgc3RhdGlzdGljcwpzdW1tYXJ5KHdhcnBicmVha3MpCmBgYAoKVGhlcmUgYXJlIHRob3VzYW5kcyBvZiBmdW5jdGlvbnMgYWNyb3NzIGh1bmRyZWRzIG9mIHBhY2thZ2VzIChleHRlcm5hbCBsaWJyYXJpZXMgb2YgZnVuY3Rpb25zIHdyaXR0ZW4gZm9yIHNwZWNpZmljIHB1cnBvc2VzLCAqZS5nLiosIGRhdGEgbWluaW5nLCBzdGF0aXN0aWNhbCBpbmZlcmVuY2UsIG1hY2hpbmUgbGVhcm5pbmcsIGltYWdlIHByb2Nlc3NpbmcsIHdlYiBkZXZlbG9wbWVudCwgdmlzdWFsaXphdGlvbiwgWE1MIHByb2Nlc3NpbmcsIFNRTCwgYW5kIHNvIGZvcnRoKS4gWW91IHdpbGwgbGVhcm4gdGhlbSBvdmVyIHRpbWUgLS0gYW5kIGl0J3MgdW5saWtlbHkgeW91IHdpbGwgZXZlciBsZWFybiBhbGwgb2YgdGhlbSwgc28gaGF2ZSBwYXRpZW5jZS4gRm9yIGEgcGFja2FnZSB0byBiZSB1c2FibGUgaW4gYW4gUiBwcm9qZWN0IGl0IG11c3QgYmUgaW5zdGFsbGVkOyBpbnN0YWxsYXRpb24gaXMgZG9uZSBvbmNlLiBUaGVuIGV2ZXJ5IHRpbWUgeW91IG5lZWQgYW4gaW5zdGFsbGVkIHBhY2thZ2UgaW4gc29tZSBSIGNvZGUsIHlvdSBtdXN0IGxvYWQgaXQgdXNpbmcgdGhlIDxjb2RlPmxpYnJhcnk8L2NvZGU+IGZ1bmN0aW9uLgoKVGhlICoqcHN5Y2gqKiBsaWJyYXJ5ICgqYWthKiBwYWNrYWdlKSBpcyBwYXJ0aWN1bGFybHkgdXNlZnVsIGZvciBzdGF0aXN0aWNhbCBhbmFseXNpcyBvZiBkYXRhLgoKYGBge3J9CiMgaW1wb3J0IHRoZSBwc3ljaCBwYWNrYWdlIC0tIGlmIHRoaXMgZmFpbHMsIHRoZW4gZmlyc3QgaW5zdGFsbCB0aGUgcGFja2FnZSBieSB1bmNvbW1lbnRpbmcgdGhlIG5leHQgbGluZQojaW5zdGFsbC5wYWNrYWdlcygicHN5Y2giKQpsaWJyYXJ5KHBzeWNoKQoKIyBkZXRhaWxlZCBkZXNjcmlwdGl2ZSBzdGF0aXN0aWNzCmRlc2NyaWJlKHdhcnBicmVha3MpCmBgYAoKSXQgaXMgbm90IHVudXN1YWwgdGhhdCBkYXRhIGlzIGRpdmlkZWQgaW50byBncm91cHMgYW5kIHRoYXQgeW91IG1heSB3YW50IGNhdGVnb3JpY2FsIHN0YXRpc3RpY3MgZm9yIGl0LiBUaGUgPGNvZGU+YWdncmVnYXRlPC9jb2RlPiBmdW5jdGlvbiBpcyBhbW9uZyB0aGUgZWFzaWVzdCBtZXRob2RzIG9mIGRvaW5nIHRoYXQuIFRoZSBkYXRhc2V0ICp3YXJwYnJlYWtzKiBoYXMgZGF0YSBmb3IgdHdvIGRpZmZlcmVudCBraW5kcyBvZiB3b29sLCBBIGFuZCBCLiBVc2luZyB0aGUgPGNvZGU+YWdncmVnYXRlPC9jb2RlPiBmdW5jdGlvbiB5b3UgY2FuIGNhbGN1bGF0ZSBzdGF0aXN0aWNzIGZvciBlYWNoIHdvb2wgc2VwYXJhdGVseS4gVGhpcyBpcyBzaW1pbGFyIHRvIGEgKipHUk9VUCBCWSoqIGNsYXVzZSBpbiBTUUwuCgpgYGB7cn0KIyBBZ2dyZWdhdGUgRnVuY3Rpb24gRXhhbXBsZTogU3VtbWFyeSBTdGF0aXN0aWNzIGJ5IEdyb3VwCmFnZ3JlZ2F0ZShicmVha3N+dGVuc2lvbiAsIGRhdGE9IHdhcnBicmVha3MsIG1lYW4pCmBgYAoKIyMgSW5zdGFsbGluZyBhbmQgTG9hZGluZyBQYWNrYWdlcwoKSW5zdGFsbGluZyBQYWNrYWdlcwoKVG8gZW5zdXJlIHRoYXQgcGFja2FnZXMgYXJlIGF1dG9tYXRpY2FsbHkgaW5zdGFsbGVkLCB5b3UgY2FuIHVzZSB0aGUgZm9sbG93aWduIGNvZGUuIFRoYXQgd2F5IHlvdXIgY29kZSBiZWNvbWVzIHBvcnRhYmxlLgoKYGBge3J9CmlmKCJSU1FMaXRlIiAlaW4lIHJvd25hbWVzKGluc3RhbGxlZC5wYWNrYWdlcygpKSA9PSBGQUxTRSkgewogIGluc3RhbGwucGFja2FnZXMoIlJTUUxpdGUiKQp9CgpsaWJyYXJ5KCJSU1FMaXRlIikKYGBgCgpJbiB0aGUgYWJvdmUgY29kZSB0aGUgZnVuY3Rpb24gPGNvZGU+aW5zdGFsbGVkLnBhY2thZ2VzKCk8L2NvZGU+IHJldHVybnMgYSBsaXN0IG9mIHRoZSBuYW1lcyBvZiBhbGwgaW5zdGFsbGVkIHBhY2thZ2VzLiBUaGUgb3BlcmF0b3IgPGNvZGU+JWluJTwvY29kZT4gaXMgYSBzZXQgb3BlcmF0b3IgdGhhdCBjaGVja3MgaWYgKiJSU1FMaXRlIiogaXMgb25lIG9mIHRoZSByZXR1cm5lZCBuYW1lcy4gSWYgaXQgaXMsIHRoZSBCb29sZWFuIGV4cHJlc3Npb24gZXZhbHVhdGVzIHRvICRUUlVFJCwgb3RoZXJ3aXNlICRGQUxTRSQuIElmIGl0IGlzIGZhbHNlLCB0aGVuIGl0IG1lYW5zIHRoZSBwYWNrYWdlIGlzIG5vdCBpbnN0YWxsZWQgYW5kIHRoZSBvcHRpb25hbCBjb2RlIHRoYXQgaW5zdGFsbHMgdGhlIHBhY2thZ2UgaXMgZXhlY3V0ZWQuIFRoZSB3YXksIHRoZSBsb2FkaW5nIG9mIHRoZSBwYWNrYWdlIHdpdGggPGNvZGU+bGlicmFyeSgiUlNRTGl0ZSIpPC9jb2RlPiBjYW5ub3QgZmFpbC4KCiMjIFNpbXBsZSBQbG90dGluZyBhbmQgVmlzdWFsIERhdGEgRXhwbG9yYXRpb24KCiMjIyBTY2F0dGVyIFBsb3QKCmBgYHtyfQpwbG90KHggPSB3YXJwYnJlYWtzJGJyZWFrcywgeSA9IHdhcnBicmVha3MkdGVuc2lvbikKYGBgCgojIyMgUS1RIFBsb3QgZm9yIE5vcm1hbGl0eSBDaGVja2luZwoKQSA0NSBkZWdyZWUgbGluZSBpbmRpY2F0ZXMgYSBub3JtYWwgZGlzdHJpYnV0aW9uIG9mIHRoZSBkYXRhLCB3aGlsZSBhICJob2NrZXkgc3RpY2siIGN1cnZlIGluZGljYXRlcyBhIG5vbi1ub3JtYWwgb3Igc2tld2VkIGRpc3RyaWJ1dGlvbi4gVGhlIGNvbHVtbiBiZWxvdyBpcyAicmVhc29uYWJseSIgbm9ybWFsbHkgZGlzdHJpYnV0ZWQuIFRoZSBzZWNvbmQgUVEgUGxvdCwgcGxvdHMgdGhlIGxvZy10cmFuc2Zvcm1lZCB2YWx1ZXMgd2hpY2ggYmV0dGVyIGZpdCBhIG5vcm1hbCAoR2F1c3NpYW4pIGRpc3RyaWJ1dGlvbi4KCmBgYHtyfQpxcW5vcm0od2FycGJyZWFrcyRicmVha3MpCnFxbm9ybShsb2cod2FycGJyZWFrcyRicmVha3MpKQpgYGAKCk5vdGUgdGhhdCB0aGUgKipncGxvdDIqKiBwYWNrYWdlIHByb3ZpZGUgbXVjaCBtb3JlIHNvcGhpc3RpY2F0ZWQgdmlzdWFsaXphdGlvbiBtZWNoYW5pc21zIGFuZCBzaG91bGQgYmUgdXNlZCBpbiBwcmFjdGljZSB0byBwcm9kdWNlIHBsb3RzIGZvciBwdWJsaWNhdGlvbi4KCiMjIERhdGEgRnJhbWUgRGltZW5zaW9ucyBhbmQgU3RydWN0dXJlCgpgYGB7cn0KbnJvdyhtdGNhcnMpCm5jb2wobXRjYXJzKQoKc3RyKG10Y2FycykKCm10Y2Fyc1tucm93KG10Y2FycyksXSAgICMgbGFzdCByb3cgb25seSBvZiBhIGRhdGEgZnJhbWUgICAKYGBgCgojIyBBZGRpbmcgYW5kIFJlbW92aW5nIENvbHVtbnMgZnJvbSBhIERhdGEgRnJhbWUKClRvIGFkZCBhIG5ldyBjb2x1bW4sIHlvdSBzaW1wbHkgImFjY2VzcyIgdGhlIGNvbHVtbiBvciB1c2UgYSBuZXcgbmFtZSBmb3IgdGhlIGNvbHVtbi4gTm90ZSBpbiB0aGUgZXhhbXBsZSBiZWxvdyB0aGF0IHlvdSBjYW4gb3BlcmF0ZSBvbiBlbnRpcmUgY29sdW1ucyAoYXMgdmVjdG9ycykgYW5kIHRoZSBvcGVyYXRpb24gaXMgYXBwbGllZCB0byBlYWNoIHBhaXIgb2YgdmFsdWVzIGluIHRoZSB0d28gdmVjdG9ycyBpbiB0aGUgb3BlcmF0aW9uLiBUaGlzIGlzIG11Y2ggbW9yZSBlZmZpY2llbnQgdGhhbiB1c2luZyBsb29wcyBhcyBpcyBuZWNlc3NhcnkgaW4gb3RoZXIgcHJvZ3JhbW1pbmcgbGFuZ3VhZ2VzLgoKYGBge3J9CiMgY29weSB0aGUgZGF0YSBmcmFtZSBtdGNhcnMgdG8gYSBuZXcgZGF0YSBmcmFtZSBkZgpkZiA8LSBtdGNhcnMKCiMgY3JlYXRlIGEgbmV3IGNvbHVtbiAiZGlzcGN5bCIgd2hpY2ggaXMgdGhlIGRpc3BsYWNlbWVudCBwZXIgY3lsaW5kZXIKZGYkZGlzcGN5bCA8LSBkZiRkaXNwIC8gZGYkY3lsCgpoZWFkKGRmKQpgYGAKCiMjIENyZWF0ZSBhIE5ldyBEYXRhIEZyYW1lCgpEYXRhIGZyYW1lcyBhcmUgY3JlYXRlZCBpbiB2YXJpb3VzIHdheXM6IHVzZSB0aGUgXDxjb2RlXDxcPmRhdGEuZnJhbWU8L2NvZGU+IGZ1bmN0aW9uLCBsb2FkIGEgQ1NWIGZpbGUsIGV4ZWN1dGUgYSBTUUwgcXVlcnksIG9yIGFzIGEgcmVzdWx0IG9mIG1hbnkgcGFja2FnZSBmdW5jdGlvbnMuCgojIyMgTG9hZCBhIERhdGEgRnJhbWUgZnJvbSBDU1YKClF1aWNrIG5vdGU6IENhcGl0YWxpemF0aW9uIGluIHBhdGggYW5kIGZpbGUgbmFtZXMgZG9lcyBub3QgbWF0dGVyIGluIFdpbmRvd3MsIGJ1dCAqKmRvZXMgbWF0dGVyKiogb24gTWFjT1MgYW5kIExpbnV4LiBGdXJ0aGVybW9yZSwgbm90ZSB0aGF0IGV2ZW4gaW4gV2luZG93cyB0aGUgcGF0aCBkZWxpbWl0ZXIgaXMgYSBmb3J3YXJkIHNsYXNoIC8gYW5kIG5vdCB0aGUgdXN1YWwgYmFja3dhcmRzIHNsYXNoIFxcLiBUaGUgXFwgaXMgYW4gImVzY2FwZSIgY2hhcmFjdGVyIGFuZCB1c2VkIHRvIGluamVjdCBub24tcHJpbnRhYmxlIGNoYXJhY3RlcnMgaW50byBhIHN0cmluZyAodGV4dCksICplLmcuKiwgIlRoaXMgc3RyaW5nIGNvbnRhaW5zICJxdW90ZXMiLiIgd2hpY2ggd291bGQgYmUgd3JpdHRlbiBpbiBSIGFzICJ0aGlzIHN0cmluZyBjb250YWlucyBcXCJxdW90ZXNcXCIuIgoKQWxzbywgdGhlIHBhcmFtZXRlcnMgPGNvZGU+aGVhZGVyID0gRjwvY29kZT4gaW5zdHJ1Y3RzIDxjb2RlPnJlYWQuY3N2PC9jb2RlPiBub3QgdG8gaW50ZXJwcmV0IHRoZSBmaXJzdCBsaW5lIGFzIGhlYWRlciBsYWJlbHMuIE9mIGNvdXJzZSwgaWYgdGhlcmUgYXJlIG5vIGxhYmVscywgdGhlbiB5b3UgbmVlZCB0byBkZWZpbmUgeW91ciBvd24uCgpBc2lkZSBmcm9tIENTViBmaWxlcywgUiBjYW4gYWxzbyBsb2FkIGEgbnVtYmVyIG9mIG90aGVyIGZpbGUgZm9ybWF0IHVzaW5nIHZhcmlvdXMgcGFja2FnZXMsIGluY2x1ZGluZyBYTUwsIEV4Y2VsLCBTUFNTLCBNYXRMYWIsIGFtb25nIG1hbnkgb3RoZXJzLgoKYGBge3IgZXZhbD1GQUxTRX0KZGYgPC0gcmVhZC5jc3YoZmlsZSA9ICJjdXN0b21lcnR4bmRhdGEuY3N2IiwgaGVhZGVyID0gRikKaGVhZChkZikKCmRmIDwtIHJlYWQuY3N2KGZpbGUgPSAiY3VzdG9tZXJ0eG5kYXRhLmNzdiIsIAogICAgICAgICAgICAgICBoZWFkZXIgPSBGLAogICAgICAgICAgICAgICBjb2wubmFtZXMgPSBjKCJudW1WaXNpdHMiLCJOdW1UeG4iLCJPUyIsIkdlbmRlciIsIlRvdFNwIikpCmhlYWQoZGYpCmBgYAoKPiBOb3RlIHRoYXQgdGhlIHZhbHVlIG9mIHRoZSAnTWFsZScgY29sdW1uIGluIHRoZSBmaXJzdCByb3cgaXMgKk5BKiB3aGljaCBpcyB0aGUgd2F5IHRoYXQgUiBpbmRpY2F0ZXMgYSBtaXNzaW5nIGRhdGEgdmFsdWUuIEl0IGlzIG5vdCAwIG9yIGFuIGVtcHR5IHN0cmluZywgaXQgaXMgdW5rbm93bi4gU28sIHN0YXRpc3RpY2FsIGZ1bmN0aW9ucyBhbmQgYWxnZWJyYWljIG9wZXJhdGlvbnMgd291bGQgcmVzdWx0IGluIGFuICpOQSogYXMgd2VsbC4KCiMjIyMgU3RyaW5ncyB2cyBGYWN0b3JzCgpUaGUgKmZhY3RvciogZGF0YSB0eXBlIGVuY29kZXMgY2F0ZWdvcmljYWwgZGF0YSwgKmUuZy4qLCB0aGUgdmFsdWUgb2YgYSB2YXJpYWJsZSBpcyBvbmUgb2YgYSBmaXhlZCB2YWx1ZSBzZXQuIE1hbnkgc3RhdGlzdGljYWwgZnVuY3Rpb25zIGluIFIgcmVxdWlyZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgdG8gYmUgb2YgdHlwZSAqZmFjdG9yKi4gSG93ZXZlciwgb2Z0ZW4sIGR1cmluZyBkYXRhIHByb2Nlc3NpbmcsIHdlIG5lZWQgdGhlIGFjdHVhbCB0ZXh0IHJhdGhlciB0aGFuIGhhdmluZyBpdCBlbmNvZGVkIGFzIGEgKmZhY3RvciogKHdoaWNoIGlzIGFjdHVhbGx5IHN0b3JlZCBpbiBSIGFzIGFuIGludGVnZXIgZm9yIGVmZmljaWVuY3kpLiBTbywgd2hlbiByZWFkaW5nIGEgQ1NWIGZpbGUgeW91IG5lZWQgdG8gZGVjaWRlIGlmIHlvdSB3YW50IHRleHQgY29sdW1ucyB0byBiZSBjaGFyYWN0ZXIgc3RyaW5ncyBvciBmYWN0b3JzIGJ5IHNldHRpbmcgdGhlIDxjb2RlPnN0cmluZ3NBc0ZhY3RvcnM8L2NvZGU+IHBhcmFtZXRlci4KCllvdSBtYXkgdXNlIGVpdGhlciA8Y29kZT5GPC9jb2RlPiBhbmQgPGNvZGU+VDwvY29kZT4gb3IgPGNvZGU+RkFMU0U8L2NvZGU+IGFuZCA8Y29kZT5UUlVFPC9jb2RlPi4KCmBgYHtyIGV2YWw9RkFMU0V9CmRmIDwtIHJlYWQuY3N2KGZpbGUgPSAiY3VzdG9tZXJ0eG5kYXRhLmNzdiIsIAogICAgICAgICAgICAgICBoZWFkZXIgPSBGLAogICAgICAgICAgICAgICBzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UsCiAgICAgICAgICAgICAgIGNvbC5uYW1lcyA9IGMoIm51bVZpc2l0cyIsIk51bVR4biIsIk9TIiwiR2VuZGVyIiwiVG90U3AiKSkKaGVhZChkZikKYGBgCgojIyMgQ3JlYXRlIGEgTmV3IERhdGEgRnJhbWUKClRoZSBjb2RlIGJlbG93IGNyZWF0ZXMgYSBuZXcgZGF0YSBmcmFtZSBmcm9tIGNvbHVtbiB2ZWN0b3JzLiBOb3RpY2UgaG93IHRoZSBjb2x1bW4gbmFtZXMgYXJlIHRoZSBuYW1lcyBvZiB0aGUgdmVjdG9ycy4gQSBuZXcgdmVjdG9yIGlzIGNyZWF0ZWQgd2l0aCB0aGUgPGNvZGU+YzwvY29kZT4gZnVuY3Rpb24sIGUuZy4sIDxjb2RlPnYgXDwtIGMoMyw1LDEsOSk8L2NvZGU+LgoKYGBge3J9CmRmMSA8LSBkYXRhLmZyYW1lKHN0YXRlID0gYygnQXJpem9uYScsJ0dlb3JnaWEnLCAnTmV3IFlvcmsnLCdJbmRpYW5hJywnV2FzaGluZ3RvbicsJ1RleGFzJyksCiAgICAgICAgICAgICAgICAgIGNvZGUgPSBhcy5mYWN0b3IoYygnQVonLCdHQScsJ05ZJywnSU4nLCdXQScsJ1RYJykpLAogICAgICAgICAgICAgICAgICBzY29yZSA9IGMoNjIsNDcsNTUsNzQsMzEsODUpKQoKaGVhZChkZjEpCgpgYGAKCiMjIFNlYXJjaCBEYXRhIEZyYW1lcwoKVGhlcmUgYXJlIHR3byBpbXBvcnRhbnQgZnVuY3Rpb25zIGZvciAic2VhcmNoaW5nIiBkYXRhIGZyYW1lczogPGNvZGU+d2hpY2g8L2NvZGU+IGFuZCA8Y29kZT5hbnk8L2NvZGU+LiBUaGUgY29kZSBiZWxvdyB1c2VzIHRoZSBidWlsdC1pbiBbKipPcmFuZ2UqKiBkYXRhIGZyYW1lXShodHRwczovL3d3dy5yZG9jdW1lbnRhdGlvbi5vcmcvcGFja2FnZXMvZGF0YXNldHMvdmVyc2lvbnMvMy42LjIvdG9waWNzL09yYW5nZSkgd2hpY2ggY29udGFpbnMgbWVhc3VyZW1lbnRzIG9mIG9yYW5nZSB0cmVlcy4gSXQgaGFzIHRocmVlIGNvbHVtbnM6IHRoZSB0cmVlLCB0aGUgKmFnZSogb2YgdGhlIHRyZWUgKGRheXMgc2luY2UgMTk2OC8xMi8zMSksIGFuZCAqY2lyY3VtZmVyZW5jZSogKGluICptbSopLgoKIyMjIHdoaWNoCgpgYGB7cn0KZGYgPC0gT3JhbmdlCgpoZWFkKGRmKQoKIyBmaW5kIGFsbCByb3dzIHdoZXJlIHRoZSBjaXJjdW1mZXJlbmNlIGlzIG1vcmUgdGhhbiAyMDBtbQpycyA8LSB3aGljaChkZiRjaXJjdW1mZXJlbmNlID4gMjAwKQoKIyBkaXNwbGF5IGFsbCByb3dzIHdoZXJlIHRoZSBjaXJjdW1mZXJlbmNlIGlzIG1vcmUgdGhhbiAyMDBtbQpkZltycyxdCgojIGNvbXBvdW5kIGNvbmRpdGlvbnMgYXJlIHBvc3NpYmxlIHdpdGggJiAoYW5kKSwgfCAob3IpLCBhbmQgISAobm90KQpyczIgPC0gd2hpY2goZGYkY2lyY3VtZmVyZW5jZSA+IDIwMCAmIGRmJGFnZSA8IDE1MDApCnJzMyA8LSB3aGljaChkZiRjaXJjdW1mZXJlbmNlIDwgMjAwIHwgIShkZiRhZ2UgPCAxNTAwKSkKcnM0IDwtIHdoaWNoKGRmJGNpcmN1bWZlcmVuY2UgPiA0MDAgfCBkZiRhZ2UgPiAxNTAwKQoKcnMyCnJzMwpyczQKCm1lYW4oZGZbcnM0LDJdKQptZWFuKGRmJGFnZVtyczNdKQoKYGBgCgpJbiB0aGUgYWJvdmUgZXhhbXBsZSA8Y29kZT5ycyBcPC0gd2hpY2goZGZcJGNpcmN1bWZlcmVuY2UgXD4gMjAwKTwvY29kZT4gZmluZHMgYWxsIHJvd3MgaW4gdGhlIGRhdGEgZnJhbWUgKmRmKiB3aGVyZSAqY2lyY3VtZmVyZW5jZSBcPiAyMDAqLiBUaGUgcm93cyBhcmUgc2F2ZWQgaW4gKnJzKi4KCiMjIyBhbnkKClRoZSA8Y29kZT5hbnk8L2NvZGU+IGZ1bmN0aW9uIHJldHVybnMgJFRSVUUkIG9yICRGQUxTRSQgZGVwZW5kaW5nIG9uIHdoZXRoZXIgYW55IGNvbHVtbiAob3Igcm93KSBpbiB0aGUgZGF0YWZyYW1lIHNhdGlzZmllcyBhIEJvb2xlYW4gZXhwcmVzc2lvbi4KCmBgYHtyfQojIGlzIHRoZXJlIGFueSB0cmVlIHdpdGggYWdlID4gMjAwMD8KYW55KGRmJGFnZSA+IDI1KQpgYGAKCiMjIFVzaW5nIFNRTCB3aXRoIERhdGEgRnJhbWVzCgpUaGUgcGFja2FnZSAqKnNxbGRmKiogYWxsb3dzIHlvdSB0byB1c2UgU1FMIHRvIGFjY2VzcywgcHJvY2Vzcywgc2VhcmNoLCBhbmQgYWdncmVnYXRlIGRhdGEgaW4gZGF0YSBmcmFtZXMuIFRoZSAqKnNxbGRmKiogcGFja2FnZSBhY3R1YWxseSBsb2FkcyB0aGUgZGF0YSBmcmFtZSBpbnRvIGFuIGluLW1lbW9yeSBTUUxpdGUgZGF0YWJhc2UuCgpGb3IgbW9yZSBpbmZvcm1hdGlvbiBvbiAqKnNxbGRmKiosIGNvbnN1bHQgW01hbmlwdWxhdGUgUiBEYXRhIEZyYW1lcyBVc2luZyBTUUxdKGh0dHBzOi8vd3d3LnJkb2N1bWVudGF0aW9uLm9yZy9wYWNrYWdlcy9zcWxkZi92ZXJzaW9ucy8wLjQtMTEjOn46dGV4dD1zcWxkZiUyMGlzJTIwYW4lMjBSJTIwcGFja2FnZSUyMGZvciUyMHJ1bm5pbmclMjBTUUwsc3VwcG9ydHMlMjBEYXRlJTIwY2xhc3MlMjBhbmQlMjBhJTIwZmV3JTIwYWRkaXRpb25hbCUyMGZ1bmN0aW9ucy4pCgpUaGUgKip0aWR5dmVyc2UqKiBwYWNrYWdlIGFsc28gY29udGFpbnMgbnVtZXJvdXMgZnVuY3Rpb25zIGZvciBwcm9jZXNzaW5nIGRhdGEgZnJhbWVzIGluIGEgU1FMLWxpa2UgbWFubmVyLgoKYGBge3J9CiNpbnN0YWxsLnBhY2thZ2VzKCJzcWxkZiIpCmxpYnJhcnkoc3FsZGYpCgojIHBlcmZvcm0gU1FMIHF1ZXJpZXMgb24gdGhlIGJ1aWx0LWluICdpcmlzJyBkYXRhIGZyYW1lCnNxbGRmKCJzZWxlY3QgKiBmcm9tIGlyaXMgbGltaXQgNSIpCnNxbGRmKCJzZWxlY3QgY291bnQoKikgZnJvbSBpcmlzIikKc3FsZGYoInNlbGVjdCBTcGVjaWVzLCBjb3VudCgqKSBmcm9tIGlyaXMgZ3JvdXAgYnkgU3BlY2llcyIpCgojIG5vdGUgdGhhdCBlYWNoIHNxbGRmIHF1ZXJ5IGFjdHVhbGx5IHJldHVybnMgYSBkYXRhIGZyYW1lCnJzIDwtIHNxbGRmKCJzZWxlY3QgU3BlY2llcywgY291bnQoKikgYXMgbnVtIGZyb20gaXJpcyBncm91cCBieSBTcGVjaWVzIikKbWVhbihycyRudW0pCmBgYAoKIyMgTG9hZCBEYXRhIGZyb20gYSBEYXRhYmFzZSB2aWEgU1FMCgpUbyByZWFkIGRhdGEgZnJvbSBhIGRhdGFiYXNlIGludG8gUiwgZm9sbG93cyB0aGVzZSBzdGVwczoKCi0gICBvcGVuIGNvbm5lY3Rpb24gdG8gZGF0YWJhc2UKLSAgIGJ1aWxkIFNRTCBxdWVyeQotICAgZXhlY3V0ZSBTUUwgcXVlcnkgYnkgc2VuZGluZyB0byBkYXRhYmFzZQotICAgY2FwdHVyZSByZXN1bHQgaW4gZGF0YWZyYW1lCgpDb25uZWN0aW5nIHRvIGEgZGF0YWJhc2UgaXMgZG9uZSBpbiBhIGRhdGFiYXNlLXNwZWNpZmljIHdheSBhbmQgZWFjaCBkYXRhYmFzZSBpcyBkaWZmZXJlbnQuIFBhY2thZ2VzIHNwZWNpZmljIHRvIHRoZSBkYXRhYmFzZSBuZWVkIHRvIGJlIGxvYWRlZCAob2YgY291cnNlLCBhZnRlciBpbnN0YWxsYXRpb24pLiBUaGUgY29kZSBiZWxvdyBhc3N1bWVzIHRoYXQgdGhlIHBhY2thZ2UgKipSU1FMaXRlKiogZm9yIGNvbm5lY3RpbmcgdG8gWypTUUxpdGUqXShodHRwczovL3NxbGl0ZS5vcmcvaW5kZXguaHRtbCkgZGF0YWJhc2VzIGlzIGluc3RhbGxlZCBidXQgbm90IGxvYWRlZC4gVG8gdXNlICpTUUxpdGUqIGZyb20gUiBkb2VzIG5vdCBhY3R1YWxseSByZXF1aXJlIHRoYXQgKlNRTGl0ZSogaXMgZG93bmxvYWRlZCBhbmQgaW5zdGFsbGVkLgoKVG8gY29ubmVjdCB0byBhIGRhdGFiYXNlIHlvdSBuZWVkIHRvIGtub3cgd2hlcmUgdGhlIGRhdGFiYXNlIGlzIGxvY2F0ZWQuIEZvciBtb3N0IGNsaWVudC9zZXJ2ZXIgZGF0YWJhc2VzIGxpa2UgTXlTUUwgeW91IG5lZWQgdG8ga25vdyB0aGUgc2VydmVyJ3MgSVAgYWRkcmVzcyBvbiB3aGljaCB0aGUgZGF0YWJhc2UgcnVucy4gRm9yICpTUUxpdGUqIHlvdSBuZWVkIHRoZSBkYXRhYmFzZSBmaWxlIHBhdGggKGFzICpTUUxpdGUqIGRvZXMgcnVuIG5vdCBvbiBhbiBhY3R1YWwgcmVtb3RlIHNlcnZlcikuCgpUbyBydW4gYSBxdWVyeSAocmV0cmlldmUgZGF0YSkgeW91IG1vc3QgY29tbW9ubHkgdXNlIHRoZSA8Y29kZT5kYkdldFF1ZXJ5PC9jb2RlPiBmdW5jdGlvbi4gVG8gcGVyZm9ybSBhbiBJTlNFUlQsIFVQREFURSwgREVMRVRFLCBDUkVBVEUgVEFCTEUsIERST1AgVEFCTEUsIEFMVEVSIFRBQkxFIHlvdSBuZWVkIHRvIHVzZSA8Y29kZT5kYlNlbmRRdWVyeTwvY29kZT4uCgpUaGUgZXhhbXBsZSBiZWxvdyBwZXJmb3JtcyBhIGRpcmVjdCBjb25uZWN0IHRvIHRoZSBkYXRhYmFzZSBhbmQgdXNlcyBmdW5jdGlvbnMgdG8gcmV0cmlldmUgZGF0YSBmcm9tIHRoZSBkYXRhYmFzZSB2aWEgU1FMLiBUaGlzIGlzIGFuIGFsdGVybmF0aXZlIHRvIGVtYmVkZGluZyBTUUwgY2h1bmtzICh7c3FsfSkgaW4gYW4gUiBOb3RlYm9vay4KCmBgYHtyfQpsaWJyYXJ5KFJTUUxpdGUpCgojIGNvbm5lY3QgdG8gdGhlIFNRTGl0ZSBkYXRhYmFzZSBpbiB0aGUgc3BlY2lmaWVkIGZpbGUKZGIuY29ubiA8LSBkYkNvbm5lY3QoU1FMaXRlKCksIGRibmFtZT0iQ29mZmVlREIuc3FsaXRlZGIiKQoKIyBjb25zdHJ1Y3QgYSBTUUwgcXVlcnkKc3FsQ21kID0gIlNFTEVDVCAqIEZST00gY29mZmVlcyIKCiMgc2VuZCB0aGUgU1FMIHF1ZXJ5IHRvIHRoZSBkYXRhYmFzZQpycyA9IGRiR2V0UXVlcnkoZGIuY29ubiwgc3FsQ21kKQoKIyBwcmludCBwYXJ0IG9mIHRoZSByZXN1bHQgdGFibGUKaGVhZChycywzKQpgYGAKCiMjIEV4YW1wbGU6IENvbXB1dGUgU3VtIG9mIE51bWJlcnMKCiMjIyBQcm9ibGVtIFN0YXRlbWVudAoKR2l2ZW4gYSB2ZWN0b3IgKG9yIGFycmF5KSBvZiBudW1iZXJzLCBjYWxjdWxhdGUgdGhlIHN1bSBvZiB0aG9zZSBudW1iZXJzLiBTb2x2ZSB0aGUgcHJvYmxlbSBmaXJzdCB1c2luZyBsb29wcyBhbmQgdGhlbiB1c2luZyByZWN1cnNpb24uIFdyaXRlIGEgZnVuY3Rpb24gYW5kIHRoZW4gY2FsbCB0aGUgZnVuY3Rpb24uIFRoZSBmdW5jdGlvbiBzaG91bGQgaWdub3JlIGFueSBub24tbnVtZXJpYyBlbGVtZW50cy4KCiMjIyBUZXN0IENhc2VzCgoxLiAgR2l2ZW4gdGhlIHZlY3RvciAqXDwyLDYsMSwwLC00LDk5XD4qLCB0aGUgZnVuY3Rpb24gc2hvdWxkIHJldHVybiAxMDQuCjIuICBHaXZlbiBhbiBlbXB0eSB2ZWN0b3IgKlw8XD4qLCB0aGUgZnVuY3Rpb24gc2hvdWxkIHJldHVybiBOQS4KMy4gIEdpdmVuIHRoZSB2ZWN0b3IgKlw8Miw2LDEsJzExJ1w+KiwgdGhlIGZ1bmN0aW9uIHNob3VsZCByZXR1cm4gOS4KNC4gIEdpdmVuIHRoZSB2ZWN0b3IgKlw8JzInLCdUd28nLCcnLCcxMSdcPiosIHRoZSBmdW5jdGlvbiBzaG91bGQgcmV0dXJuIDAuCjUuICBHaXZlbiB0aGUgZW1wdHkgdmVjdG9yICpcPFw+KiwgdGhlIGZ1bmN0aW9uIHNob3VsZCByZXR1cm4gMC4KCiMjIyBTYW1wbGUgU29sdXRpb24KCkxldCdzIHN0YXJ0IGJ5IHdvcmtpbmcgb3V0IHRoZSBhbGdvcml0aG0gZm9yIG9ubHkgbnVtYmVycyBhbmQgbm90ICh5ZXQpIHVzaW5nIGEgZnVuY3Rpb24uIFdlIGNhbiBjYWxjdWxhdGUgdGhlIHN1bSBieSBhZGRpbmcgZWFjaCBudW1iZXIgdG8gc29tZSAiYWNjdW11bGF0b3IiIHZhcmlhYmxlLCAqZS5nLiosIHRoZSBzdW0gb2YgKlw8Miw2LDFcPiogaXMgKnggPSAyLCB4ID0geCArIDYsIHggPSB4ICsgMSouIEluIHRoaXMgZXhhbXBsZSwgKngqIGlzIHRoZSBhY2N1bXVsYXRvciB2YXJpYWJsZS4gVXNpbmcgYW4gYWNjdW11bGF0b3IgaXMgYSBjb21tb24gcHJhY3RpY2UgaW4gdGhlc2UgdHlwZXMgb2YgcHJvYmxlbXMuIFRoZSBhY2N1bXVsYXRvciBjb3VsZCBlaXRoZXIgc3RhcnQgYXQgMCBvciBhdCB0aGUgZmlyc3QgZWxlbWVudC4gSGF2aW5nIGl0IHN0YXJ0IGF0IDAgaXMgc2ltcGxlciBiZWNhdXNlIGl0IHdvdWxkIGFjY291bnQgZm9yIGFuIGVtcHR5IHZlY3RvciB0aGF0IGRvZXNuJ3QgaGF2ZSBhIGZpcnN0IGVsZW1lbnQuCgpXaGVuIHlvdSB3cml0ZSAqeCA9IHggKyAxKiwgcmVtZW1iZXIgdGhhdCB0aGUgZXZhbHVhdGlvbiBvZiAqPSogaXMgZnJvbSByaWdodCB0byBsZWZ0LCAqaS5lLiosIHRoZSByaWdodCBzaWRlIGlzIGV2YWx1YXRlZCBmaXJzdCBhbmQgdGhlbiB0aGUgdmFsdWUgb2YgdGhlIHJlc3VsdCBvZiB0aGF0IGV4cHJlc3Npb24gaXMgYXNzaWduZWQgdG8gdGhlIHZhcmlhYmxlIG9uIHRoZSBsZWZ0IHNpZGUuIExldCdzIHNheSB0aGF0ICp4ID0gNSogYmVmb3JlIHlvdSB3cml0ZSB0aGUgYWZvcmVtZW50aW9uZWQgc3RhdGVtZW50LiBTbywgdGhlIGV4cHJlc3Npb24gKnggKyAxKiBpcyAqNSArIDEqIHdoaWNoIGV2YWx1YXRlcyB0byAqNiouIFRoYXQgdmFsdWUgaXMgdGhlbiBhc3NpZ25lZCB0byAqeCosIHNvIGFmdGVyIHRoYXQgKnggPSA2Ki4KCmBgYHtyfQp2ID0gYygzLCA2LCAxKSAgICAgICAgICMgYSB2ZWN0b3IvYXJyYXkgb2YgbnVtYmVycwoKeCA9IDAgICAgICAgICAgICAgICAgICAjIHggaXMgb3VyIGFjY3VtdWxhdG9yOyBpdCBzdGFydHMgYXQgMAoKIyBsb29wIHRocm91Z2ggZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IKZm9yIChpIGluIDE6bGVuZ3RoKHYpKSB7CiAgIyBhZGQgdGhlIG5leHQgZWxlbWVudCBpbiB0aGUgdmVjdG9yIHRvIHgKICB4ID0gKHggKyB2W2ldKQp9CgpwcmludCAoeCkKYGBgCgpXaGF0IHdvdWxkIGhhcHBlbiBpZiB0aGUgdmVjdG9yIGlzIGVtcHR5PyBUZXN0IHRoZSBhYm92ZSBjb2RlLiBOb3RlIHRoYXQgaXQgc3RpbGwgd29ya3MgaWYgPGNvZGU+diA9IGMoKTwvY29kZT4uIFRlc3QgaXQgd2l0aCBuZWdhdGl2ZSBudW1iZXJzIGluIHRoZSB2ZWN0b3IuIEl0IHN0aWxsIHdvcmtzLiBCdXQgd2hhdCBhYm91dCBzdHJpbmdzPyBOb3cgaXQgZmFpbHMuIFNvLCB3ZSBuZWVkIHRvIGltcHJvdmUgdGhlIHByb2dyYW0gdG8gaWdub3JlIG5lZ2F0aXZlIG51bWJlcnMuIEFsbCBwcm9ncmFtbWluZyBsYW5ndWFnZXMgaGF2ZSBzb21lIHdheSBvZiBndWFyZGluZyBhZ2FpbnN0IHRoYXQuIFNvbWUgbGFuZ3VhZ2VzIGxpa2UgSmF2YSBhbmQgQysrIHJlcXVpcmUgdGhhdCBhbGwgZWxlbWVudHMgb2YgYSB2ZWN0b3IgYXJlIG9mIHRoZSBzYW1lIGRlY2xhcmVkIHR5cGUsIHNvIGFkZGluZyBhIHN0cmluZyB3b3VsZCBjYXVzZSBhIGNvbXBpbGUtdGltZSBlcnJvci4gTm8gd29ycmllcyBpbiB0aG9zZSBsYW5ndWFnZXMuIEJ1dCB1bnR5cGVkIGFuZCB1bmNvbXBpbGVkIGxhbmd1YWdlcyBsaWtlIFIsIFB5dGhvbiwgYW5kIEphdmFTY3JpcHQgcmVxdWlyZSBydW4tdGltZSBjaGVja3MuIFNvLCBsZXQncyBhZGQgb25lLiBXZSBuZWVkIGEgZnVuY3Rpb24gdGhhdCBjaGVja3MgdGhlIHR5cGUgb2YgYSB2YXJpYWJsZS4gUiBoYXMgZnVuY3Rpb25zIHN1Y2ggYXMgPGNvZGU+aXMubnVtZXJpYzwvY29kZT4gZm9yIHRoYXQgcHVycG9zZS4KCkJ1dCB0aGVyZSBpcyBhbm90aGVyIHByb2JsZW0uIFZlY3RvcnMgaW4gUiBhcmUgb2YgYSBzaW5nbGUgdHlwZSwgKmkuZS4qLCBhbGwgZWxlbWVudHMgbXVzdCBiZSBvZiB0aGUgc2FtZSB0eXBlLiBSIGF0dGVtcHRzIHRvIGNvZXJjZSAoKmFrYSogY2FzdCkgdGhlIGVsZW1lbnRzIGluIHRoZSB2ZWN0b3IgdG8gYSBjb21tb24gdHlwZS4gU2luY2UgYSBzdHJpbmcgY2Fubm90IGJlIGNvbnZlcnRlZCB0byBhIG51bWJlciwgaXQnbGwgY29udmVydCB0aGUgbnVtYmVycyB0byB0ZXh0LiBUcnkgaXQgb3V0OiB3aGF0IGlzIHRoZSB2YWx1ZSBvZiAqdlsxXSo/IEl0J3MgKiIzIiogLS0gYSBzdHJpbmcuIFNvLCB3ZSBuZWVkIHRvIGNvbnZlcnQgZWFjaCBlbGVtZW50IHRvIGEgbnVtYmVyIGFuZCBpZ25vcmUgdGhlIG51bWJlciBpdCBmYWlscy4gPGNvZGU+YXMubnVtZXJpYzwvY29kZT4gd2lsbCBhdHRlbXB0IGEgY29udmVyc2lvbiBvZiBhbnkgdGV4dCBjb250YWluaW5nIGEgbnVtYmVyIHRvIGEgbnVtYmVyLCAqZS5nLiogaXQgd2lsbCBjb252ZXJ0ICoiMyIqIHRvICozKiBhbmQgKiIzLjE0IiogdG8gKjMuMTQqLiBBZ2FpbiwgaWYgeW91IGFyZSBpbiBkb3VidCBvciBhcmUgbm90IHN1cmUsIHRyeSBpdCBvdXQgLS0gZXhwZXJpbWVudC4gSW4gZmFjdCwgY3JlYXRlIGEgbmV3IE5vdGVib29rIG9yIGp1c3Qgb3BlbiB1cCB0aGUgUiBjb25zb2xlIGFuZCB0eXBlIGluIHRoZSBzdGF0ZW1lbnRzOyBzZWUgd2hhdCBoYXBwZW5zLgoKYGBge3J9CnYgPSBjKDMsIDYsICJ0d28iLCAxKQpwcmludCh2WzFdKQpwcmludChhcy5udW1lcmljKHZbMV0pKQpwcmludChhcy5udW1lcmljKHZbM10pKQpgYGAKClNvLCBpZiB0aGUgY29udmVyc2lvbiB0byBhIG51bWJlciBpcyBub3QgcG9zc2libGUsIGl0IHdpbGwgcmV0dXJuICpOQSouICpOQSogaXMgc2ltaWxhciB0byAqbnVsbCogb3IgKm5pbCogaW4gbWFueSBvdGhlciBsYW5ndWFnZXMuIFdlIGNhbiBjaGVjayBvZiBhIHZhbHVlIGlzICpOQSogYnkgdXNpbmcgdGhlIGZ1bmN0aW9uIDxjb2RlPmlzLm5hPC9jb2RlPjsgd2UgY2Fubm90IHNpbXBseSBzYXkgPGNvZGU+aWYgKHZbaV0gPT0gTkEpPC9jb2RlPiAtLSAqTkEqIGlzIG5vdCBhIHZhbHVlIHNvIHlvdSBjYW5ub3QgdXNlIHRoZSBjb21wYXJpc29uIG9wZXJhdG9yLiBNYW55IG90aGVyIGxhbmd1YWdlcyB3b3JrIHRoZSBzYW1lIHdheS4KCmBgYHtyLCB3YXJuaW5nID0gRkFMU0V9CnYgPSBjKDMsIDYsICJ0d28iLCAxKSAgICAgICAgIAoKeCA9IDAgICAgICAgICAgICAgICAgICAgICAgICAgIyB4IGlzIG91ciBhY2N1bXVsYXRvcjsgaXQgc3RhcnRzIGF0IDAKCiMgbG9vcCB0aHJvdWdoIGVhY2ggZWxlbWVudCBvZiB0aGUgdmVjdG9yCmZvciAoaSBpbiAxOmxlbmd0aCh2KSkgewogICMgYXR0ZW1wdCB0byBjb252ZXJ0IHRoZSB0ZXh0IHRvIGEgbnVtYmVyCiAgayA9IGFzLm51bWVyaWModltpXSkKICAjIGFkZCB0aGUgbmV4dCBlbGVtZW50IGluIHRoZSB2ZWN0b3IgdG8geCBpZiBpdCdzIG5vdCBOQQogIGlmICghaXMubmEoaykpCiAgICB4ID0gKHggKyBrKQp9CgpwcmludCAoeCkKYGBgCgpEb2VzIG91ciBjb2RlIHN0aWxsIHdvcmsgaWYgdGhlIHZlY3RvciBpcyBhbGwgbnVtYmVycz8gV2hhdCBpZiBpdCdzIGFsbCBzdHJpbmdzPyBMZXQncyBjaGVjayB0aGF0LiBSZW1lbWJlciB0byBhbHdheXMgdGVzdCBwcmlvciB0ZXN0IGNhc2VzIHRvIGVuc3VyZSB0aGF0IHNvbWUgbmV3IGNvZGUgZGlkIG5vdCBicmVhayB5b3VyIG9sZCBjb2RlLiBTb2Z0d2FyZSBkZXZlbG9wZXJzIGNhbGwgdGhhdCAqcmVncmVzc2lvbiB0ZXN0aW5nKi4KCmBgYHtyLCB3YXJuaW5nID0gRkFMU0V9CnYgPSBjKDMsIDYsIDIsIDEpICAgICAgICAgCgp4ID0gMCAgICAgICAgICAgICAgICAgICAgICAgICAjIHggaXMgb3VyIGFjY3VtdWxhdG9yOyBpdCBzdGFydHMgYXQgMAoKIyBsb29wIHRocm91Z2ggZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IKZm9yIChpIGluIDE6bGVuZ3RoKHYpKSB7CiAgIyBhdHRlbXB0IHRvIGNvbnZlcnQgdGhlIHRleHQgdG8gYSBudW1iZXIKICBrID0gYXMubnVtZXJpYyh2W2ldKQogICMgYWRkIHRoZSBuZXh0IGVsZW1lbnQgaW4gdGhlIHZlY3RvciB0byB4IGlmIGl0J3Mgbm90IE5BCiAgaWYgKCFpcy5uYShrKSkKICAgIHggPSAoeCArIGspCn0KCnByaW50ICh4KQpgYGAKCkluZGVlZCwgaXQgc3RpbGwgd29ya3MuIE5vdyB3aGF0IGFib3V0IGFsbCB0ZXh0IG9yIGVtcHR5Li4uIHRoaXMgaXMgZ2V0dGluZyBkaWZmaWN1bHQgd2l0aG91dCByZXBlYXRpbmcgY29kZS4gSWYgeW91IGZpbmQgeW91cnNlbGYgY29weWluZyBhbmQgcGFzdGluZyBjb2RlLCBpdCBtZWFucyB0aGF0IHlvdSBuZWVkIGEgZnVuY3Rpb24uIExldCdzIHB1dCB0aGUgY29kZSBpbnRvIGEgZnVuY3Rpb24uIFdlJ2xsIGFsc28gYWRkIGNvZGUgdG8gZ3VhcmQgYWdhaW5zdCBhbiBlbXB0eSB2ZWN0b3IuCgpgYGB7ciwgd2FybmluZyA9IEZBTFNFfQpzdW1WZWN0b3IgPC0gZnVuY3Rpb24gKHYpCnsKICB4ID0gMCAgICAjIHggaXMgYW4gYWNjdW11bGF0b3I7IGl0IHN0YXJ0cyBhdCAwCiAgCiAgaWYgKGxlbmd0aCh2KSA9PSAwKQogICAgcmV0dXJuICgwKQogIAogICMgbG9vcCB0aHJvdWdoIGVhY2ggZWxlbWVudCBvZiB0aGUgdmVjdG9yCiAgZm9yIChpIGluIDE6bGVuZ3RoKHYpKSB7CiAgICAjIGF0dGVtcHQgdG8gY29udmVydCB0aGUgdGV4dCB0byBhIG51bWJlcgogICAgayA9IGFzLm51bWVyaWModltpXSkKICAgICMgYWRkIHRoZSBuZXh0IGVsZW1lbnQgaW4gdGhlIHZlY3RvciB0byB4IGlmIGl0J3Mgbm90IE5BCiAgICBpZiAoIWlzLm5hKGspKQogICAgICB4ID0gKHggKyBrKQogIH0KICAKICByZXR1cm4gKHgpCn0KYGBgCgpRdWljayBjb21tZW50IG9uIFI6IHN0cmluZ3MgY2FuIGJlIGVuY2xvc2VkIGluIGVpdGhlciBkb3VibGUgb3Igc2luZ2xlIHF1b3RlLCAqZS5nLiosICondGV4dCcqIGlzIHRoZSBzYW1lIGFzICoidGV4dCIqLiBXaGV0aGVyIHlvdSB1c2Ugc2luZ2xlIG9yIGRvdWJsZSBxdW90ZXMgZGVwZW5kcyBvbiBjb250ZXh0LiBGb3IgZXhhbXBsZSwgaWYgeW91IHdhbnQgdG8gdXNlIHRoZSBzdHJpbmcgKkJvYidzIENhciosIHRoZW4geW91IHdvdWxkIG5lZWQgdG8gZW5jbG9kZSB0aGF0IGluIGRvdWJsZSBxdW90ZXM6ICoiQm9iJ3MgQ2FyIiouCgpgYGB7ciwgd2FybmluZyA9IEZBTFNFfQp2ID0gYygyLDYsMSwwLC00LDk5KSAgICAgICAgIAp4ID0gc3VtVmVjdG9yKHYpCnByaW50ICh4KQoKdiA9IGMoMiw2LDEsJzExJykgICAgICAgICAKeCA9IHN1bVZlY3Rvcih2KQpwcmludCAoeCkKCnYgPSBjKCkgICAgICAgICAKeCA9IHN1bVZlY3Rvcih2KQpwcmludCAoeCkKCnYgPSBjKCcyJywnVHdvJywnJywnMTEnKSAgICAgICAgIAp4ID0gc3VtVmVjdG9yKHYpCnByaW50ICh4KQpgYGAKClRoaXMgdGFrZXMgY2FyZSBvZiBvdXIgb3JpZ2luYWxseSBkZWZpbmVkIHRlc3QgY2FzZXMuIEFyZSB0aGVyZSB0ZXN0IGNhc2VzIHdlIGZvcmdvdCB0byBhY2NvdW50IGZvcj8gQ2FuIHlvdSB0aGluayBvZiBvdGhlciBzaXR1YXRpb25zPyBXaGF0IGlmIHNvbWVvbmUgcGFzc2VkIGEgKmxpc3QqIG9yIGEgKm1hdHJpeCogb3IgYSBzaW5nbGUgbnVtYmVyPyBXb3VsZCBpdCBzdGlsbCB3b3JrPyBJbiBSLCBQeXRob24sIGFuZCBKYXZhU2NyaXB0LCBhcyB3ZWxsIGFzIG90aGVyIG5vbi1jb21waWxlZCBsYW5ndWFnZXMsIHlvdSBuZWVkIHRvIGFkZCBtYW55IG1vcmUgcnVuLXRpbWUgY2hlY2tzLgoKT25lIHF1aWNrIHByb2dyYW1taW5nOiB0aGUgdmFyaWFibGUgKngqIGluIHRoZSBmdW5jdGlvbiBpcyBsb2NhbCB0byB0aGUgZnVuY3Rpb24gYW5kIGlzIG5vdCBrbm93biBvciBldmVuIHZpc2libGUgb3V0c2lkZSB0aGUgZnVuY3Rpb24uIFNvLCBpdCdzIGEgdG90YWxseSBkaWZmZXJlbnQgdmFyaWFibGUgdGhhbiB0aGUgKngqIGluIHRoZSB0ZXN0IGNvZGUuIFRoaXMgaXMgc28gYmVjYXVzZSBSIHVzZXMsIGxpa2UgbW9zdCBtb2Rlcm4gbGFuZ3VhZ2VzLCBsb2NhbCBzY29waW5nLiBBbnl0aGluZyBkZWNsYXJlZCB3aXRoaW4gY3VybHkgYnJhY2VzIHsuLi59IGlzIGxvY2FsIHRvIHRoYXQgc2NvcGUuCgpgYGB7ciwgd2FybmluZyA9IEZBTFNFfQp2ID0gOTkgICAgICAgICAKeCA9IHN1bVZlY3Rvcih2KQpwcmludCAoeCkKCnYgPSBsaXN0KDMsIGMoMzQsIDU1LCA5OSkpICAKCiMgdGhpcyB3aWxsIG5vdCB3b3JrIGFzIHYgaXMgYSBsaXN0IG5vdCB0aGUgZXhwZWN0ZWQgdmVjdG9yCiMgICB4ID0gc3VtVmVjdG9yKHYpCnByaW50ICh4KQpgYGAKCkl0IHdvcmtzIGZvciBzaW5nbGUgbnVtYmVycyBidXQgbm90IGZvciBsaXN0cywgc28gbGV0J3MgYWRkIGEgY2hlY2sgdG8gZW5zdXJlIHRoYXQgdGhlIHBhc3NlZCBhcmd1bWVudCBpcyBhIHZlY3Rvci4gQWdhaW4sIHRoaXMgaXMgYSBjb21tb24gbmVlZCBmb3IgbWFueSBsYW5ndWFnZXM6IHJ1bi10aW1lIHR5cGUgY2hlY2tpbmcuCgpgYGB7ciwgd2FybmluZyA9IEZBTFNFfQpzdW1WZWN0b3IgPC0gZnVuY3Rpb24gKHYpCnsKICAjIGlmIHYgaXMgYSBsaXN0IG9yIG5vdCBhIHZlY3RvciwgcmV0dXJuIDAKICBpZiAoIWlzLnZlY3Rvcih2KSB8fCBpcy5saXN0KHYpKQogICAgcmV0dXJuICgwKQogIAogIGlmIChsZW5ndGgodikgPT0gMCkKICAgIHJldHVybiAoMCkKICAKICAjIHYgaXMgYSB2YWxpZCB2ZWN0b3I7IGxldCdzIGFkZCB0aGUgbnVtYmVycyBhbmQgaWdub3JlIHN0cmluZ3MKICAKICB4ID0gMCAgICAjIHggaXMgYW4gYWNjdW11bGF0b3I7IGl0IHN0YXJ0cyBhdCAwCiAgCiAgIyBsb29wIHRocm91Z2ggZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IKICBmb3IgKGkgaW4gMTpsZW5ndGgodikpIHsKICAgICMgYXR0ZW1wdCB0byBjb252ZXJ0IHRoZSB0ZXh0IHRvIGEgbnVtYmVyCiAgICBrID0gYXMubnVtZXJpYyh2W2ldKQogICAgIyBhZGQgdGhlIG5leHQgZWxlbWVudCBpbiB0aGUgdmVjdG9yIHRvIHggaWYgaXQncyBub3QgTkEKICAgIGlmICghaXMubmEoaykpCiAgICAgIHggPSAoeCArIGspCiAgfQogIAogIHJldHVybiAoeCkKfQpgYGAKCmBgYHtyLCB3YXJuaW5nID0gRkFMU0V9CnYgPSA5OSAgICAgICAgIAp4ID0gc3VtVmVjdG9yKHYpCnByaW50ICh4KQoKdiA9IGxpc3QoMywgYygzNCwgNTUsIDk5KSkgICAgICAgICAKeCA9IHN1bVZlY3Rvcih2KQpwcmludCAoeCkKYGBgCgpUaGVyZSBpcyBhbiBpbnRlcmVzdGluZyBwcm9ncmFtbWluZyBkZXNpZ24gYXJndW1lbnQgaW4gdGhlIGFib3ZlIGNvZGU6IHdoYXQgaXMgdGhlIGNvcnJlY3QgcmV0dXJuIHZhbHVlIHdoZW4gdGhlIHBhc3NlZCBhcmd1bWVudCBpcyBub3QgYSB2ZWN0b3I/IFNob3VsZCBpdCBiZSAqMCogb3Igc2hvdWxkIGl0IGJlICpOQSogYXMgaXQgY2Fubm90IGJlIGNvbXB1dGVkLiBHZW5lcmFsbHksIHJldHVybmluZyAqMCogaW1wbGllcyB0aGF0IHRoZSBjYWxjdWxhdGlvbiB3YXMgc3VjY2Vzc2Z1bCBhbmQgZXZhbHVhdGVkIHRvICowKiwgYnV0IHRoYXQncyBub3QgdGhlIGNhc2UgaGVyZSwgc28gcmV0dXJuaW5nICpOQSogbWlnaHQgYWxsb3cgdGhlIGNhbGxlciBvZiB0aGUgZnVuY3Rpb24gdG8gY2F0Y2ggdGhhdC4gSW4gSmF2YSBhbmQgQysrIHdlIG1pZ2h0IGhhdmUgdGhyb3duIGFuIGV4Y2VwdGlvbiwgYnV0IFIgZG9lcyBub3Qgc3VwcG9ydCBleGNlcHRpb25zLgoKPiBOb3RlIGhvdyB3ZSBidWlsdCB0aGUgY29kZSBpbiBzdGFnZXMuIEl0IHdhcyBub3QgYWxsIGRvbmUgYXQgb25jZS4gU3RhcnQgc2ltcGxlLCBrZWVwIGFkZGluZyB0byBpdCwgdGFrZSBjYXJlIG9mIG1vcmUgYW5kIG1vcmUgc2l0dWF0aW9ucy4gRXZlbnR1YWxseSB5b3UgaGF2ZSBzb2x2ZWQgdGhlIGVudGlyZSBwcm9ibGVtLgoKIyMjIyBOYXRpdmUgUiBTb2x1dGlvbgoKQmVmb3JlIHdlIGxlYXZlIHRoaXMgZXhhbXBsZSwgbGV0J3MgdGFrZSBhIGxvb2sgYXQgYSBtb3JlICJuYXRpdmUiIFIgaW1wbGVtZW50YXRpb24gdGhhdCB0YWtlcyBhZHZhbnRhZ2Ugb2YgdGhlIGluaGVyZW50IHZlY3RvciBwcm9jZXNzaW5nIGNhcGFiaWxpdGllcyAoYWxvbmdzaWRlIHBvdGVudGlhbCBoYXJkd2FyZS1iYXNlZCB2ZWN0b3JpemF0aW9uIG9mIHRoZSBjb2RlKSBhbmQgYXR0ZW5kYW50IHNpZ25pZmljYW50IHBlcmZvcm1hbmNlIGltcHJvdmVtZW50cy4KCmBgYHtyfQp2ID0gYygyLDYsMSwwLC00LDk5KSAgICAgICAgIAp4ID0gc3VtKHYpCnByaW50ICh4KQpgYGAKClRoZSBzb2x1dGlvbiBiZWxvdyBwcmludHMgbm90IGp1c3QgdGhlIHN1bSBvZiB0aGUgZWxlbWVudHMgYnV0IHRoZSBzdW0gb2Ygc3F1YXJlcyBvZiB0aGUgZWxlbWVudHMuIE5vdGljZSBob3cgdGhlIFIgaW1wbGVtZW50YXRpb24gZG9lcyBub3QgcmVxdWlyZSB0aGUgdXNlIG9mIGEgbG9vcCBiZWNhdXNlIGFueSBvcGVyYXRpb24gb24gYSB2ZWN0b3IgaXMgYXV0b21hdGljYWxseSBjYXJyaWVkIG91dCBmb3IgZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IgLS0gaW4gZWZmZWN0IHRoZSBsb29wIGlzIGltcGxpZWQuCgpgYGB7cn0KdiA9IGMoMiw2LDEsMCwtNCw5OSkgICAgICAgICAKeCA9IHN1bSh2IF4gMikKcHJpbnQgKHgpCmBgYAoKIyMgRXhhbXBsZTogRmluZCBUaW1lIERpZmZlcmVuY2UKCiMjIyBQcm9ibGVtIFN0YXRlbWVudAoKR2l2ZW4gdHdvIHRpbWUgdmFsdWVzIGJhc2VkIG9uIGEgMjQgaG91ciBjbG9jaywgZGV0ZXJtaW5lIGhvdyBtdWNoIHRpbWUgaGFzIGVsYXBzZWQgYmV0d2VlbiB0aGUgZmlyc3QgYW5kIHRoZSBzZWNvbmQgdGltZS4gVGhlIHRpbWUgaXMgZ2l2ZW4gaW4gdGhlIGZvcm1hdCBISDpNTTpTUy4gSEggaXMgYmV0d2VlbiAwIGFuZCAyMywgYW5kIE1NIGFuZCBTUyBhcmUgYmV0d2VlbiAwIGFuZCA1OS4gVmFsdWVzIGxlc3MgdGhhbiAxMCBoYXZlIGEgbGVhZGluZyB6ZXJvLCAqZS5nLiosIDA3OjE1OjAwLiBNaWRuaWdodCBpcyAwMDowMAoKVGhlIG91dHB1dCBzaG91bGQgYXQgZmlyc3QgYmUgdGhlIG51bWJlciBvZiBzZWNvbmRzIGJldHdlZW4gdGhlIHR3byB0aW1lIHZhbHVlcy4gVGhlbiwgdGhlIHByb2dyYW0gc2hvdWxkIGJlIGltcHJvdmVkIHRvIGRpc3BsYXkgdGhlIGRpZmZlcmVuY2UgaW4gdGhlIG51bWJlciBvZiBob3VycywgdGhlIG51bWJlciBvZiBtaW51dGVzLCBhbmQgdGhlIG51bWJlciBvZiBzZWNvbmRzIHRoYXQgaGF2ZSBwYXNzZWQgZnJvbSB0aGUgZmlyc3QgdG8gdGhlIHNlY29uZCB0aW1lLCBpbiB0aGUgZm9ybSAqKkhIIEhPVVJTIE1NIE1JTlVURVMgU1MgU0VDT05EUyoqLgoKSWYgdGhlIHNlY29uZCB0aW1lIGlzICJiZWZvcmUiIHRoZSBmaXJzdCB0aW1lLCBhc3N1bWUgdGhhdCBpdCBpcyB0aGUgZm9sbG93aW5nIGRheS4KCiMjIyBUZXN0IENhc2VzCgotICAgMTA6MDM6NDMgMTU6MDA6NTggc2hvdWxkIGRpc3BsYXkgNCBIT1VSUyA1NyBNSU5VVEVTIDE1IFNFQ09ORFMKLSAgIDA3OjI1OjAwIDIwOjUyOjE0IHNob3VsZCBkaXNwbGF5IDEzIEhPVVJTIDI3IE1JTlVURVMgMTQgU0VDT05EUwotICAgMTY6MzA6MzAgMDU6NDA6MTAgc2hvdWxkIGRpc3BsYXkgMTMgSE9VUlMgOSBNSU5VVEVTIDQwIFNFQ09ORFMKCiMjIyBTYW1wbGUgU29sdXRpb24KCiMjIyMgU29sdXRpb24gSQoKQSBmZXcgcXVpY2sgZXhwbGFuYXRpb25zIG9uIFIgc3ludGF4LiBUaGUgcGVyaW9kIChkb3QpIGlzIGNvbnNpZGVyZWQgYSB2YWxpZCBjaGFyYWN0ZXIgZm9yIGlkZW50aWVycyBpbiBSOyBpdCBpcyBub3QgYSBwcm9wZXJ0eSBhY2Nlc3Mgb3BlcmF0b3IgbGlrZSBpbiBKYXZhIG9yIEMrKy4gRk9yIGFzc2lnbm1lbnQsIG9uZSBjYW4gdXNlIDxjb2RlPj08L2NvZGU+IG9yIDxjb2RlPlw8LTwvY29kZT4gd2l0aCB0aGUgbGF0dGVyIGJlaW5nIG1vcmUgY29tbW9uLgoKVGhpcyBzb2x1dGlvbiBjb252ZXJ0cyBlYWNoIHRpbWUgdmFsdWUgaW50byBzZWNvbmRzIGFuZCB0aGVuIHRha2VzIHRoZSBkaWZmZXJlbmNlLCByZXN1bHRpbmcgaW4gdGhlIHRpbWUgZGlmZmVyZW5jZSBpbiBzZWNvbmRzIGFzIGxvbmcgYXMgd2UgZG8gbm90IGNyb3NzIGEgZGF5IGJvdW5kYXJ5LgoKYGBge3J9CiMgZGVmaW5lIHR3byB0aW1lIHZhbHVlcyBicm9rZW4gZG93biBpbnRvIHRocmVlIHZhcmlhYmxlcwoKdDEuaGggPSAyMAp0MS5tbSA9IDAwCnQxLnNzID0gMDAKCnQyLmhoID0gMjMKdDIubW0gPSAwMQp0Mi5zcyA9IDMwCgojIGNvbnZlcnQgZWFjaCB0aW1lIHZhbHVlIHRvIGFsbCBzZWNvbmRzCgp0MSA9ICgodDEuaGggKiA2MCAqIDYwKSArICh0MS5tbSAqIDYwKSArIHQxLnNzKQp0MiA9ICgodDIuaGggKiA2MCAqIDYwKSArICh0Mi5tbSAqIDYwKSArIHQyLnNzKQoKZCA9IHQyIC0gdDEKCnByaW50KGQpCmBgYAoKIyMjIyBTb2x1dGlvbiBJSQoKSW4gdGhpcyBpbXByb3ZlbWVudCBzdGVwLCB3ZSB3aWxsIGNvbnZlcnQgdGhlIHJlc3VsdCBmcm9tIHNlY29uZHMgaW50byB0aGUgcmVxdWlyZWQgZm9ybWF0LiBPbmUgaXNzdWUgd2l0aCBpbnRlZ2VyIGRpdmlzaW9uIGluIG1vc3QgbGFuZ3VhZ2VzIGlzIHRoYXQgaXQgd2lsbCByZXN1bHQgaW4gYSBmcmFjdGlvbiAoZmxvYXRpbmcgcG9pbnQgbnVtYmVyKS4gV2Ugd2lsbCBuZWVkIHRvIHJvdW5kIGRvd24gb3IgY29lcmNlIHRoZSByZXN1bHQgYmFjayBpbnRvIGFuIGludGVnZXIuIFNvLCB3ZSB3aWxsIGZpcnN0IGZpbmQgdGhlIHRvdGFsIG51bWJlciBvZiBob3VycyBpbiB0aGUgZGlmZmVyZW5jZSBieSBkaXZpZGluZyB0aGUgZGlmZmVyZW5jZSBpbiBzZWNvbmRzIGJ5IDM2MCAoNjAgXCogNjAgc2Vjb25kcyBwZXIgaG91cikuIFRoZSByZW1haW5pbmcgc2Vjb25kcyBhcmUgdGhlbiBjb252ZXJ0ZWQgaW50byBtaW51dGVzLCBhbmQgZmluYWxseSwgdGhlIHJlbWFpbmluZyBzZWNvbmRzIGFyZSBsZWZ0IG92ZXIuIFBlcmZvcm0gdGhlIGNhbGN1bGF0aW9uIGJ5IGhhbmQgb24gYSBwaWVjZSBvZiBwYXBlciBhbmQgZW5zdXJlIHRoYXQgeW91IHVuZGVyc3RhbmQgb3VyICJhbGdvcml0aG0iLiBJbiBmYWN0LCB1c2luZyBleGFtcGxlcyBhbmQgd29ya2luZyBpdCBvdXQgYnkgaGFuZCB3aWxsIGhlbHAgeW91IGVudmlzaW9uIGhvdyB5b3UgbWlnaHQgcHJvZ3JhbSB0aGlzLgoKQXMgYW4gYXNpZGUsIHRoZSBjYWxjdWxhdGlvbiBvZiB0aGUgcmVtYWluZGVyIGNvdWxkIGhhdmUgYWxzbyBiZWVuIGRvbmUgdXNpbmcgdGhlIG1vZHVsdXMgb3BlcmF0b3I7IGp1c3QgZ29lcyB0byBzaG93IHRoYXQgdGhlcmUgaXMgb2Z0ZW4gbW9yZSB0aGFuIG9uZSBnb29kIHdheSB0byBzb2x2ZSBhIHByb2dyYW1taW5nIHByb2JsZW0uIE5ldmVyIGJlIGFmcmFpZCB0byBleHBlcmltZW50LCBidXQgc3RhcnQgd2l0aCB0aGUgc2ltcGxlc3Qgc29sdXRpb24gZmlyc3QuIFdvcnJ5IGFib3V0IGNvcnJlY3RuZXNzIGZpcnN0LCB0aGVuIGFib3V0IGVsZWdhbmNlIGFuZCBzcGVlZCBvZiBleGVjdXRpb24uCgpJbiB0aGUgY29kZSBiZWxvdywgdGhlIDxjb2RlPnBhc3RlKCk8L2NvZGU+IGZ1bmN0aW9uIGlzIHVzZWQgaW4gUiB0byBjb25jYXRlbmF0ZSBzdHJpbmdzLiA8Y29kZT5wYXN0ZSgpPC9jb2RlPiBpbnNlcnRzIGEgc3BhY2UgYmV0d2VlbiB0aGUgc3RyaW5ncywgd2hpbGUgPGNvZGU+cGFzdGUwKCk8L2NvZGU+IGRvZXMgbm90LgoKYGBge3J9CiMgZGVmaW5lIHR3byB0aW1lIHZhbHVlcyBicm9rZW4gZG93biBpbnRvIHRocmVlIHZhcmlhYmxlcwoKdDEuaGggPSAwMAp0MS5tbSA9IDMwCnQxLnNzID0gMDAKCnQyLmhoID0gMDMKdDIubW0gPSAzMAp0Mi5zcyA9IDMwCgojIGNvbnZlcnQgZWFjaCB0aW1lIHZhbHVlIHRvIGFsbCBzZWNvbmRzCgp0MSA9ICgodDEuaGggKiA2MCAqIDYwKSArICh0MS5tbSAqIDYwKSArIHQxLnNzKQp0MiA9ICgodDIuaGggKiA2MCAqIDYwKSArICh0Mi5tbSAqIDYwKSArIHQyLnNzKQoKZCA9IHQyIC0gdDEKCiMgZmluZCBudW1iZXIgb2YgaG91cnMsIG1pbnV0ZXMsIGFuZCBzZWNvbmRzCgojIGNvbnZlcnQgc2Vjb25kcyB0byB3aG9sZSBob3VycwpoaCA9IGFzLmludGVnZXIoZCAvICg2MCAqIDYwKSkKCiMgZmluZCB0aGUgcmVtYWluaW5nIHNlY29uZHMKciA9IChkIC0gKGhoICogKDYwICogNjApKSkKCiMgY29udmVydCBzZWNvbmRzIHRvIHdob2xlIG1pbnV0ZXMKbW0gPSBhcy5pbnRlZ2VyKHIgLyA2MCkKCiMgZmluZCB0aGUgcmVtYWluaW5nIHNlY29uZHMgKHVzaW5nIHRoZSBtb2Qgb3BlcmF0b3IgdGhpcyB0aW1lKQpzcyA9ICggciAtIChtbSAqIDYwKSkKCiMgZm9ybWF0IHRoZSByZXF1aXJlZCBvdXRwdXQKb3V0IDwtIHBhc3RlKGhoLCAiSE9VUlMiLCBtbSwgIk1JTlVURVMiLCBzcywgIlNFQ09ORFMiKQpwcmludChvdXQpCmBgYAoKQW4gaXNzdWUgd2l0aCBTb2x1dGlvbiBJSSBpcyB0aGF0IGl0IGRvZXMgbm90IGNvbnNpZGVyIGRheSBib3VuZGFyaWVzLCBzbyBsZXQncyB3b3JrIG9uIHRoYXQgbmV4dC4gRXhhbXBsZTogV2hhdCBpcyB0aGUgdGltZSBkaWZmZXJlbmNlIGJldHdlZW4gMjM6MDA6MDAgYW5kIDAzOjAwOjAwPyBJdCBpcyBleGFjdGx5IGZvdXIgaG91cnMgYXMgaXQncyAyM2ggdG9kYXkgYW5kIDNoIHRoZSBuZXh0IG1vcm5pbmcgLS0gd2UgYXJlIGNyb3NzaW5nIGRheXMuIFNvLCBob3cgZG8gd2UgaW1wbGVtZW50IHRoaXM/IE9uZSBhcHByb2FjaCBpcyB0byBjaGVjayBpZiB0aW1lICMxIGlzIGJlZm9yZSBvciBhZnRlciB0aW1lICMyLCAqaS5lLiosIG9uZSB2YWx1ZSBpcyBsYXJnZXIgb3Igc21hbGxlciB0aGFuIHRoZSBvdGhlci4gRm9yIHRoZSBub3JtYWwgY2FzZSwgdGltZSAjMSBcPCB0aW1lICMyLCBidXQgaWYgdGhlIGRheSBib3VuZGFyeSBpcyBjcm9zc2VkLCB0aGVuIHRpbWUgIzEgXD4gdGltZSAjMi4gSWYgdGhleSBhcmUgZXF1YWwsIHRoZW4gdGhlIGRpZmZlcmVuY2UgaXMgemVybyBhbmQgaXQgZG9lc24ndCBtYXR0ZXIgd2hpY2ggY2FsY3VsYXRpb24geW91IHVzZS4gTm93LCB3aGVuIHdlIGRldGVjdCB0aGF0IHRpbWUgIzEgXD4gdGltZSAjMiwgdGhlbiB3ZSBuZWVkIHRvIGNhbGN1bGF0ZSB0aGUgdGltZSByZW1haW5pbmcgdW50aWwgbWlkbmlnaHQgYW5kIHRoZW4gdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiBtaWRuaWdodCBhbmQgdGhlIHRpbWUgdGhlIG5leHQgZGF5IGFuZCBhZGQgdGhvc2UgdHdvIHRpbWUgdmFsdWVzLgoKU28sIHdlIGhhdmUgdHdvIHRpbWUgY2FsY3VsYXRpb25zIC0tIG1pZ2h0IGJlIGJldHRlciB0byBmaXJzdCBkZWZpbmUgYSBmdW5jdGlvbiBzbyB3ZSBkbyBub3QgaGF2ZSBkdXBsaWNhdGUgY29kZS4gVGhlIGZ1bmN0aW9uIHdpbGwgY2FsY3VsYXRlIHRoZSB0aW1lIGRpZmZlcmVuY2UgYW5kIHJldHVybiB0aGUgdGltZSBkaWZmZXJlbmNlIGluIHNlY29uZHMuCgojIyMjIFNvbHV0aW9uIElJSQoKTGV0J3MganVzdCB3cml0ZSB0aGUgZnVuY3Rpb24gZmlyc3Qgd2l0aG91dCB3b3JyeWluZyBhYm91dCB0aGUgZGF5IGJvdW5kYXJ5IGNyb3NzaW5nLgoKVGhlIGNvZGUgYmVsb3cgbWFrZXMgdXNlIG9mIHRoZSBSIDxjb2RlPnN1YnN0cigpPC9jb2RlPiBmdW5jdGlvbiB3aGljaCBleHRyYWN0cyBjaGFyYWN0ZXJzIGZyb20gYSB0ZXh0IHN0cmluZyBzdGFydGluZyBhdCBvbmUgcG9zaXRpb24gYW5kIGVuZGluZyBhdCBhbm90aGVyIHBvc2l0aW9uLiBGb3IgZXhhbXBsZSwgPGNvZGU+c3Vic3RyKCJhYmNkZWYiLCAyLCA0KTwvY29kZT4gcmVzdWx0cyBpbiAqImJjZCIqLiBFdmVyeSBwcm9ncmFtbWluZyBsYW5ndWFnZSBoYXMgYSBzaW1pbGFyIGZ1bmN0aW9uLCBhbHRob3VnaCBpdCBtaWdodCByZXF1aXJlIGFuIGV4dGVybmFsIHN0cmluZyBsaWJyYXJ5LiBUaGUgcmVzdWx0IG9mIGFuIGV4dHJhY3Rpb24gZnJvbSBhIHN0cmluZyBpcyBhIHN0cmluZyBkZXNwaXRlIGJlaW5nIGp1c3QgZGlnaXRzIC0tIDEyIGlzIG5vdCB0aGUgc2FtZSBhcyAnMTInLiBPbmUgaXMgaW50ZXJwcmV0ZWQgYnkgYSBjb21wdXRlciBwcm9ncmFtIGFzIGFuIGludGVnZXIgd2hpbGUgdGhlIG90aGVyIGlzIHRleHQgKGEgc3RyaW5nKS4gV2UgbmVlZCB0byBjb252ZXJ0LiBUTyBjb252ZXJ0IGEgc3RyaW5nIG9mIGRpZ2l0cyB0byBhbiBpbnRlZ2VyLCB1c2UgPGNvZGU+YXMuaW50ZWdlcigpPC9jb2RlPiBpbiBSOyBvdGhlciBsYW5ndWFnZXMgaGF2ZSBzaW1pbGFyIGZ1bmN0aW9ucy4KCmBgYHtyfQojIEZVTkNUSU9OOiB0aW1lRGlmZiAodDEsIHQyKQojIENhbGN1bGF0ZXMgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0d28gdGltZSB2YWx1ZXMgaW4gdGhlIGZvcm0gSEg6TU06U1MKIyBSZXR1cm5zIHRoZSBkaWZmZXJlbmNlIGluIHNlY29uZHMuCgp0aW1lRGlmZiA8LSBmdW5jdGlvbiAodDEsIHQyKQp7CiAgdDEuaGggPSBhcy5pbnRlZ2VyKHN1YnN0cih0MSwgMSwgMikpCiAgdDEubW0gPSBhcy5pbnRlZ2VyKHN1YnN0cih0MSwgNCwgNSkpCiAgdDEuc3MgPSBhcy5pbnRlZ2VyKHN1YnN0cih0MSwgNywgOCkpCiAgCiAgdDIuaGggPSBhcy5pbnRlZ2VyKHN1YnN0cih0MiwgMSwgMikpCiAgdDIubW0gPSBhcy5pbnRlZ2VyKHN1YnN0cih0MiwgNCwgNSkpCiAgdDIuc3MgPSBhcy5pbnRlZ2VyKHN1YnN0cih0MiwgNywgOCkpCiAgCiAgIyBjb252ZXJ0IGVhY2ggdGltZSB2YWx1ZSB0byBhbGwgc2Vjb25kcwogIAogIHQxID0gKCh0MS5oaCAqIDYwICogNjApICsgKHQxLm1tICogNjApICsgdDEuc3MpCiAgdDIgPSAoKHQyLmhoICogNjAgKiA2MCkgKyAodDIubW0gKiA2MCkgKyB0Mi5zcykKICAKICBkID0gdDIgLSB0MQogIAogIHJldHVybiAoZCkKfQpgYGAKCmBgYHtyfQojIyMjIyMjIyBURVNUIENPREUgIyMjIyMjIyMgCgp0MSA9ICIwMDowMDowMCIKdDIgPSAiMDM6NTk6NTkiCgpkIDwtIHRpbWVEaWZmKHQxLCB0MikKCiMgY29udmVydCBzZWNvbmRzIHRvIHdob2xlIGhvdXJzCmhoID0gYXMuaW50ZWdlcihkIC8gKDYwICogNjApKQoKIyBmaW5kIHRoZSByZW1haW5pbmcgc2Vjb25kcwpyID0gKGQgLSAoaGggKiAoNjAgKiA2MCkpKQoKIyBjb252ZXJ0IHNlY29uZHMgdG8gd2hvbGUgbWludXRlcwptbSA9IGFzLmludGVnZXIociAvIDYwKQoKIyBmaW5kIHRoZSByZW1haW5pbmcgc2Vjb25kcyAodXNpbmcgdGhlIG1vZCBvcGVyYXRvciB0aGlzIHRpbWUpCnNzID0gc3MgPSAoIHIgLSAobW0gKiA2MCkpCgojIGZvcm1hdCB0aGUgcmVxdWlyZWQgb3V0cHV0Cm91dCA8LSBwYXN0ZShoaCwgIkhPVVJTIiwgbW0sICJNSU5VVEVTIiwgc3MsICJTRUNPTkRTIikKcHJpbnQob3V0KQpgYGAKCk5vdGUgaG93IHdlIGFkZGVkIGEgdGVzdGluZyBjb2RlIGJsb2NrLiAqKlJlbWVtYmVyOiBhbHdheXMgcGVyZm9ybSB1bml0IHRlc3RpbmcgYW5kIHRlc3QgeW91ciBmdW5jdGlvbnMuKioKClNvLCBub3cgbGV0J3MgZGVhbCB3aXRoIHRoZSBkYXkgYm91bmRhcnkgY3Jvc3NpbmcgaXNzdWUuCgojIyMjIFNvbHV0aW9uIElWCgpgYGB7cn0KIyBGVU5DVElPTjogdGltZURpZmYgKHQxLCB0MikKIyBDYWxjdWxhdGVzIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdHdvIHRpbWUgdmFsdWVzIGluIHRoZSBmb3JtIEhIOk1NOlNTCiMgUmV0dXJucyB0aGUgZGlmZmVyZW5jZSBpbiBzZWNvbmRzLgoKdGltZURpZmYgPC0gZnVuY3Rpb24gKHQxLCB0MikKewogIHQxLmhoID0gYXMuaW50ZWdlcihzdWJzdHIodDEsIDEsIDIpKQogIHQxLm1tID0gYXMuaW50ZWdlcihzdWJzdHIodDEsIDQsIDUpKQogIHQxLnNzID0gYXMuaW50ZWdlcihzdWJzdHIodDEsIDcsIDgpKQogIAogIHQyLmhoID0gYXMuaW50ZWdlcihzdWJzdHIodDIsIDEsIDIpKQogIHQyLm1tID0gYXMuaW50ZWdlcihzdWJzdHIodDIsIDQsIDUpKQogIHQyLnNzID0gYXMuaW50ZWdlcihzdWJzdHIodDIsIDcsIDgpKQogIAogICMgY29udmVydCBlYWNoIHRpbWUgdmFsdWUgdG8gYWxsIHNlY29uZHMKICAKICB0MS5zZWNzID0gKCh0MS5oaCAqIDYwICogNjApICsgKHQxLm1tICogNjApICsgdDEuc3MpCiAgdDIuc2VjcyA9ICgodDIuaGggKiA2MCAqIDYwKSArICh0Mi5tbSAqIDYwKSArIHQyLnNzKQogIAogICMgaXMgdDEgPCB0Mj8KICBpZiAodDEuc2VjcyA8PSB0Mi5zZWNzKSB7CiAgICBkID0gdDIuc2VjcyAtIHQxLnNlY3MKICB9IGVsc2UgewogICAgIyB3ZSBhcmUgY3Jvc3NpbmcgYSBkYXkgYm91bmRhcnksIHNvIGxldCdzIGZpbmQgdGhlIHRpbWUKICAgICMgdW50aWwgbWlkbmlnaHQgYW5kIHRoZW4gdGhlIHRpbWUgZnJvbSBtaWRuaWdodCB0bwogICAgIyB0aGUgc2Vjb25kIHRpbWU7IG5vdGUgdGhlIHJlY3Vyc2l2ZSBjYWxsIGFuZCBhZGRpbmcKICAgICMgb25lIGV4dHJhIHNlY29uZCBzaW5jZSB3ZSBhcmUgZ29pbmcgdW50aWwgdGhlIHRpbWUKICAgICMgdGhhdCBpcyBvbmUgbWludXRlIGJlZm9yZSBtaWRuaWdodCBhcyBtaWRuaWdodCBpcyAKICAgICMgMDA6MDA6MDAgYW5kIHRoYXQgd291bGQgYnJlYWsgdGhlIGNvZGUKICAgIAogICAgdHRtID0gKHRpbWVEaWZmKHQxLCAiMjM6NTk6NTkiKSArIDEpCiAgICB0YWYgPSAodGltZURpZmYoIjAwOjAwOjAwIiwgdDIpKQogICAgCiAgICBkID0gKHR0bSArIHRhZikKICB9CiAgCiAgcmV0dXJuIChkKQp9CmBgYAoKYGBge3J9CiMjIyMjIyMjIFRFU1QgQ09ERSAjIyMjIyMjIyAKCnQxID0gIjIzOjMwOjQ1Igp0MiA9ICIwMzoxMjowMCIKCmQgPC0gdGltZURpZmYodDEsIHQyKQoKIyBjb252ZXJ0IHNlY29uZHMgdG8gd2hvbGUgaG91cnMKaGggPSBhcy5pbnRlZ2VyKGQgLyAoNjAgKiA2MCkpCgojIGZpbmQgdGhlIHJlbWFpbmluZyBzZWNvbmRzCnIgPSAoZCAtIChoaCAqICg2MCAqIDYwKSkpCgojIGNvbnZlcnQgc2Vjb25kcyB0byB3aG9sZSBtaW51dGVzCm1tID0gYXMuaW50ZWdlcihyIC8gNjApCgojIGZpbmQgdGhlIHJlbWFpbmluZyBzZWNvbmRzICh1c2luZyB0aGUgbW9kIG9wZXJhdG9yIHRoaXMgdGltZSkKc3MgPSAociAtIChtbSAqIDYwKSkKCiMgZm9ybWF0IHRoZSByZXF1aXJlZCBvdXRwdXQKb3V0IDwtIHBhc3RlKGhoLCAiSE9VUlMiLCBtbSwgIk1JTlVURVMiLCBzcywgIlNFQ09ORFMiKQpwcmludChvdXQpCmBgYAoKSG93IHdvdWxkIHlvdSBzb2x2ZSB0aGUgcHJvYmxlbSB3aXRob3V0IHRoZSB1c2Ugb2YgcmVjdXJzaW9uPyBJcyB0aGF0IHNvbHV0aW9uIG1vcmUgZWxlZ2FudD8gRWFzaWVyIHRvIHVuZGVyc3RhbmQ/CgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiMjIEZpbGVzICYgUmVzb3VyY2VzCgpgYGB7ciB6aXBGaWxlcywgZWNobz1GQUxTRX0KemlwTmFtZSA9IHNwcmludGYoIkxlc3NvbkZpbGVzLSVzLSVzLnppcCIsIAogICAgICAgICAgICAgICAgIHBhcmFtcyRjYXRlZ29yeSwKICAgICAgICAgICAgICAgICBwYXJhbXMkbnVtYmVyKQoKdGV4dEFMaW5rID0gcGFzdGUwKCJBbGwgRmlsZXMgZm9yIExlc3NvbiAiLCAKICAgICAgICAgICAgICAgcGFyYW1zJGNhdGVnb3J5LCIuIixwYXJhbXMkbnVtYmVyKQoKIyBkb3dubG9hZEZpbGVzTGluaygpIGlzIGluY2x1ZGVkIGZyb20gX2luc2VydDJEQi5SCmtuaXRyOjpyYXdfaHRtbChkb3dubG9hZEZpbGVzTGluaygiLiIsIHppcE5hbWUsIHRleHRBTGluaykpCmBgYAoKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgojIyBSZWZlcmVuY2VzCgpObyByZWZlcmVuY2VzLgoKIyMgRXJyYXRhCgpbTGV0IHVzIGtub3ddKGh0dHBzOi8vZm9ybS5qb3Rmb3JtLmNvbS8yMTIxODcwNzI3ODQxNTcpe3RhcmdldD0iX2JsYW5rIn0uCg==