Linear and Polynomial Regression for Pumpkin Pricing - Lesson 3

Infographic by Dasani Madipalli

Introduction

So far you have explored what regression is with sample data gathered from the pumpkin pricing dataset that we will use throughout this lesson. You have also visualized it using ggplot2.💪

Now you are ready to dive deeper into regression for ML. In this lesson, you will learn more about two types of regression: basic linear regression and polynomial regression, along with some of the math underlying these techniques.

Throughout this curriculum, we assume minimal knowledge of math, and seek to make it accessible for students coming from other fields, so watch for notes, 🧮 callouts, diagrams, and other learning tools to aid in comprehension.

Preparation

As a reminder, you are loading this data so as to ask questions of it.

  • When is the best time to buy pumpkins?

  • What price can I expect of a case of miniature pumpkins?

  • Should I buy them in half-bushel baskets or by the 1 1/9 bushel box? Let’s keep digging into this data.

In the previous lesson, you created a tibble (a modern reimagining of the data frame) and populated it with part of the original dataset, standardizing the pricing by the bushel. By doing that, however, you were only able to gather about 400 data points and only for the fall months. Maybe we can get a little more detail about the nature of the data by cleaning it more? We’ll see… 🕵️‍♀️

For this task, we’ll require the following packages:

  • tidyverse: The tidyverse is a collection of R packages designed to makes data science faster, easier and more fun!

  • tidymodels: The tidymodels framework is a collection of packages for modeling and machine learning.

  • janitor: The janitor package provides simple little tools for examining and cleaning dirty data.

  • corrplot: The corrplot package provides a visual exploratory tool on correlation matrix that supports automatic variable reordering to help detect hidden patterns among variables.

You can have them installed as:

install.packages(c("tidyverse", "tidymodels", "janitor", "corrplot"))

The script below checks whether you have the packages required to complete this module and installs them for you in case they are missing.

suppressWarnings(if (!require("pacman")) install.packages("pacman"))

pacman::p_load(tidyverse, tidymodels, janitor, corrplot)

We’ll later load these awesome packages and make them available in our current R session. (This is for mere illustration, pacman::p_load() already did that for you)

1. A linear regression line

As you learned in Lesson 1, the goal of a linear regression exercise is to be able to plot a line of best fit to:

  • Show variable relationships. Show the relationship between variables

  • Make predictions. Make accurate predictions on where a new data point would fall in relationship to that line.

To draw this type of line, we use a statistical technique called Least-Squares Regression. The term least-squares means that all the data points surrounding the regression line are squared and then added up. Ideally, that final sum is as small as possible, because we want a low number of errors, or least-squares. As such, the line of best fit is the line that gives us the lowest value for the sum of the squared errors - hence the name least squares regression.

We do so since we want to model a line that has the least cumulative distance from all of our data points. We also square the terms before adding them since we are concerned with its magnitude rather than its direction.

🧮 Show me the math

This line, called the line of best fit can be expressed by an equation:

Y = a + bX

X is the ‘explanatory variable or predictor’. Y is the ‘dependent variable or outcome’. The slope of the line is b and a is the y-intercept, which refers to the value of Y when X = 0.

Infographic by Jen Looper

First, calculate the slope b.

In other words, and referring to our pumpkin data’s original question: “predict the price of a pumpkin per bushel by month”, X would refer to the price and Y would refer to the month of sale.

Infographic by Jen Looper

Calculate the value of Y. If you’re paying around $4, it must be April!

The math that calculates the line must demonstrate the slope of the line, which is also dependent on the intercept, or where Y is situated when X = 0.

You can observe the method of calculation for these values on the Math is Fun web site. Also visit this Least-squares calculator to watch how the numbers’ values impact the line.

Not so scary, right? 🤓

Correlation

One more term to understand is the Correlation Coefficient between given X and Y variables. Using a scatterplot, you can quickly visualize this coefficient. A plot with datapoints scattered in a neat line have high correlation, but a plot with datapoints scattered everywhere between X and Y have a low correlation.

A good linear regression model will be one that has a high (nearer to 1 than 0) Correlation Coefficient using the Least-Squares Regression method with a line of regression.

2. A dance with data: creating a data frame that will be used for modelling

Artwork by @allison_horst

Load up required libraries and dataset. Convert the data to a data frame containing a subset of the data:

  • Only get pumpkins priced by the bushel

  • Convert the date to a month

  • Calculate the price to be an average of high and low prices

  • Convert the price to reflect the pricing by bushel quantity

We covered these steps in the previous lesson.

# Load the core Tidyverse packages
library(tidyverse)
library(lubridate)

# Import the pumpkins data
pumpkins <- read_csv(file = "https://raw.githubusercontent.com/microsoft/ML-For-Beginners/main/2-Regression/data/US-pumpkins.csv")


# Get a glimpse and dimensions of the data
glimpse(pumpkins)
## Rows: 1,757
## Columns: 26
## $ `City Name`       <chr> "BALTIMORE", "BALTIMORE", "BALTIMORE", "BALTIMORE", ~
## $ Type              <chr> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Package           <chr> "24 inch bins", "24 inch bins", "24 inch bins", "24 ~
## $ Variety           <chr> NA, NA, "HOWDEN TYPE", "HOWDEN TYPE", "HOWDEN TYPE",~
## $ `Sub Variety`     <chr> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Grade             <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Date              <chr> "4/29/17", "5/6/17", "9/24/16", "9/24/16", "11/5/16"~
## $ `Low Price`       <dbl> 270, 270, 160, 160, 90, 90, 160, 160, 160, 160, 160,~
## $ `High Price`      <dbl> 280, 280, 160, 160, 100, 100, 170, 160, 170, 160, 17~
## $ `Mostly Low`      <dbl> 270, 270, 160, 160, 90, 90, 160, 160, 160, 160, 160,~
## $ `Mostly High`     <dbl> 280, 280, 160, 160, 100, 100, 170, 160, 170, 160, 17~
## $ Origin            <chr> "MARYLAND", "MARYLAND", "DELAWARE", "VIRGINIA", "MAR~
## $ `Origin District` <chr> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ `Item Size`       <chr> "lge", "lge", "med", "med", "lge", "lge", "med", "lg~
## $ Color             <chr> NA, NA, "ORANGE", "ORANGE", "ORANGE", "ORANGE", "ORA~
## $ Environment       <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ `Unit of Sale`    <chr> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Quality           <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Condition         <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Appearance        <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Storage           <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Crop              <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ Repack            <chr> "E", "E", "N", "N", "N", "N", "N", "N", "N", "N", "N~
## $ `Trans Mode`      <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ ...25             <lgl> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
## $ ...26             <chr> NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, NA, ~
# Print the first 50 rows of the data set
pumpkins %>% 
  slice_head(n = 5)

In the spirit of sheer adventure, let’s explore the janitor package that provides simple functions for examining and cleaning dirty data. For instance, let’s take a look at the column names for our data:

# Return column names
pumpkins %>% 
  names()
##  [1] "City Name"       "Type"            "Package"         "Variety"        
##  [5] "Sub Variety"     "Grade"           "Date"            "Low Price"      
##  [9] "High Price"      "Mostly Low"      "Mostly High"     "Origin"         
## [13] "Origin District" "Item Size"       "Color"           "Environment"    
## [17] "Unit of Sale"    "Quality"         "Condition"       "Appearance"     
## [21] "Storage"         "Crop"            "Repack"          "Trans Mode"     
## [25] "...25"           "...26"

🤔 We can do better. Let’s make these column names friendR by converting them to the snake_case convention using janitor::clean_names. To find out more about this function: ?clean_names

# Clean names to the snake_case convention
pumpkins <- pumpkins %>% 
  clean_names(case = "snake")

# Return column names
pumpkins %>% 
  names()
##  [1] "city_name"       "type"            "package"         "variety"        
##  [5] "sub_variety"     "grade"           "date"            "low_price"      
##  [9] "high_price"      "mostly_low"      "mostly_high"     "origin"         
## [13] "origin_district" "item_size"       "color"           "environment"    
## [17] "unit_of_sale"    "quality"         "condition"       "appearance"     
## [21] "storage"         "crop"            "repack"          "trans_mode"     
## [25] "x25"             "x26"

Much tidyR 🧹! Now, a dance with the data using dplyr as in the previous lesson! 💃

# Select desired columns
pumpkins <- pumpkins %>% 
  select(variety, city_name, package, low_price, high_price, date)



# Extract the month from the dates to a new column
pumpkins <- pumpkins %>%
  mutate(date = mdy(date),
         month = month(date)) %>% 
  select(-date)



# Create a new column for average Price
pumpkins <- pumpkins %>% 
  mutate(price = (low_price + high_price)/2)


# Retain only pumpkins with the string "bushel"
new_pumpkins <- pumpkins %>% 
  filter(str_detect(string = package, pattern = "bushel"))


# Normalize the pricing so that you show the pricing per bushel, not per 1 1/9 or 1/2 bushel
new_pumpkins <- new_pumpkins %>% 
  mutate(price = case_when(
    str_detect(package, "1 1/9") ~ price/(1.1),
    str_detect(package, "1/2") ~ price*2,
    TRUE ~ price))

# Relocate column positions
new_pumpkins <- new_pumpkins %>% 
  relocate(month, .before = variety)


# Display the first 5 rows
new_pumpkins %>% 
  slice_head(n = 5)

Good job!👌 You now have a clean, tidy data set on which you can build your new regression model!

Mind a scatter plot?

# Set theme
theme_set(theme_light())

# Make a scatter plot of month and price
new_pumpkins %>% 
  ggplot(mapping = aes(x = month, y = price)) +
  geom_point(size = 1.6)

A scatter plot reminds us that we only have month data from August through December. We probably need more data to be able to draw conclusions in a linear fashion.

Let’s take a look at our modelling data again:

# Display first 5 rows
new_pumpkins %>% 
  slice_head(n = 5)

What if we wanted to predict the price of a pumpkin based on the city or package columns which are of type character? Or even more simply, how could we find the correlation (which requires both of its inputs to be numeric) between, say, package and price? 🤷🤷

Machine learning models work best with numeric features rather than text values, so you generally need to convert categorical features into numeric representations.

This means that we have to find a way to reformat our predictors to make them easier for a model to use effectively, a process known as feature engineering.

3. Preprocessing data for modelling with recipes 👩‍🍳👨‍🍳

Activities that reformat predictor values to make them easier for a model to use effectively has been termed feature engineering.

Different models have different preprocessing requirements. For instance, least squares requires encoding categorical variables such as month, variety and city_name. This simply involves translating a column with categorical values into one or more numeric columns that take the place of the original.

For example, suppose your data includes the following categorical feature:

city
Denver
Nairobi
Tokyo

You can apply ordinal encoding to substitute a unique integer value for each category, like this:

city
0
1
2

And that’s what we’ll do to our data!

In this section, we’ll explore another amazing Tidymodels package: recipes - which is designed to help you preprocess your data before training your model. At its core, a recipe is an object that defines what steps should be applied to a data set in order to get it ready for modelling.

Now, let’s create a recipe that prepares our data for modelling by substituting a unique integer for all the observations in the predictor columns:

# Specify a recipe
pumpkins_recipe <- recipe(price ~ ., data = new_pumpkins) %>% 
  step_integer(all_predictors(), zero_based = TRUE)


# Print out the recipe
pumpkins_recipe
## 
## -- Recipe ----------------------------------------------------------------------
## 
## -- Inputs
## Number of variables by role
## outcome:   1
## predictor: 6
## 
## -- Operations
## * Integer encoding for: all_predictors()

Awesome! 👏 We just created our first recipe that specifies an outcome (price) and its corresponding predictors and that all the predictor columns should be encoded into a set of integers 🙌! Let’s quickly break it down:

  • The call to recipe() with a formula tells the recipe the roles of the variables using new_pumpkins data as the reference. For instance the price column has been assigned an outcome role while the rest of the columns have been assigned a predictor role.

  • step_integer(all_predictors(), zero_based = TRUE) specifies that all the predictors should be converted into a set of integers with the numbering starting at 0.

We are sure you may be having thoughts such as: “This is so cool!! But what if I needed to confirm that the recipes are doing exactly what I expect them to do? 🤔”

That’s an awesome thought! You see, once your recipe is defined, you can estimate the parameters required to actually preprocess the data, and then extract the processed data. You don’t typically need to do this when you use Tidymodels (we’ll see the normal convention in just a minute-> workflows) but it can come in handy when you want to do some kind of sanity check for confirming that recipes are doing what you expect.

For that, you’ll need two more verbs: prep() and bake() and as always, our little R friends by Allison Horst help you in understanding this better!

Artwork by @allison_horst

prep(): estimates the required parameters from a training set that can be later applied to other data sets. For instance, for a given predictor column, what observation will be assigned integer 0 or 1 or 2 etc

bake(): takes a prepped recipe and applies the operations to any data set.

That said, lets prep and bake our recipes to really confirm that under the hood, the predictor columns will be first encoded before a model is fit.

# Prep the recipe
pumpkins_prep <- prep(pumpkins_recipe)

# Bake the recipe to extract a preprocessed new_pumpkins data
baked_pumpkins <- bake(pumpkins_prep, new_data = NULL)

# Print out the baked data set
baked_pumpkins %>% 
  slice_head(n = 10)

Woo-hoo!🥳 The processed data baked_pumpkins has all it’s predictors encoded confirming that indeed the preprocessing steps defined as our recipe will work as expected. This makes it harder for you to read but much more intelligible for Tidymodels! Take some time to find out what observation has been mapped to a corresponding integer.

It is also worth mentioning that baked_pumpkins is a data frame that we can perform computations on.

For instance, let’s try to find a good correlation between two points of your data to potentially build a good predictive model. We’ll use the function cor() to do this. Type ?cor() to find out more about the function.

# Find the correlation between the city_name and the price
cor(baked_pumpkins$city_name, baked_pumpkins$price)
## [1] 0.3236397
# Find the correlation between the package and the price
cor(baked_pumpkins$package, baked_pumpkins$price)
## [1] 0.6061713

As it turns out, there’s only weak correlation between the City and Price. However there’s a bit better correlation between the Package and its Price. That makes sense, right? Normally, the bigger the produce box, the higher the price.

While we are at it, let’s also try and visualize a correlation matrix of all the columns using the corrplot package.

# Load the corrplot package
library(corrplot)

# Obtain correlation matrix
corr_mat <- cor(baked_pumpkins %>% 
                  # Drop columns that are not really informative
                  select(-c(low_price, high_price)))

# Make a correlation plot between the variables
corrplot(corr_mat, method = "shade", shade.col = NA, tl.col = "black", tl.srt = 45, addCoef.col = "black", cl.pos = "n", order = "original")

🤩🤩 Much better.

A good question to now ask of this data will be: ‘What price can I expect of a given pumpkin package?’ Let’s get right into it!

Note: When you bake() the prepped recipe pumpkins_prep with new_data = NULL, you extract the processed (i.e. encoded) training data. If you had another data set for example a test set and would want to see how a recipe would pre-process it, you would simply bake pumpkins_prep with new_data = test_set

4. Build a linear regression model

Infographic by Dasani Madipalli

Now that we have build a recipe, and actually confirmed that the data will be pre-processed appropriately, let’s now build a regression model to answer the question: What price can I expect of a given pumpkin package?

Train a linear regression model using the training set

As you may have already figured out, the column price is the outcome variable while the package column is the predictor variable.

To do this, we’ll first split the data such that 80% goes into training and 20% into test set, then define a recipe that will encode the predictor column into a set of integers, then build a model specification. We won’t prep and bake our recipe since we already know it will preprocess the data as expected.

set.seed(2056)
# Split the data into training and test sets
pumpkins_split <- new_pumpkins %>% 
  initial_split(prop = 0.8)


# Extract training and test data
pumpkins_train <- training(pumpkins_split)
pumpkins_test <- testing(pumpkins_split)



# Create a recipe for preprocessing the data
lm_pumpkins_recipe <- recipe(price ~ package, data = pumpkins_train) %>% 
  step_integer(all_predictors(), zero_based = TRUE)



# Create a linear model specification
lm_spec <- linear_reg() %>% 
  set_engine("lm") %>% 
  set_mode("regression")

Good job! Now that we have a recipe and a model specification, we need to find a way of bundling them together into an object that will first preprocess the data (prep+bake behind the scenes), fit the model on the preprocessed data and also allow for potential post-processing activities. How’s that for your peace of mind!🤩

In Tidymodels, this convenient object is called a workflow and conveniently holds your modeling components! This is what we’d call pipelines in Python.

So let’s bundle everything up into a workflow!📦

# Hold modelling components in a workflow
lm_wf <- workflow() %>% 
  add_recipe(lm_pumpkins_recipe) %>% 
  add_model(lm_spec)

# Print out the workflow
lm_wf
## == Workflow ====================================================================
## Preprocessor: Recipe
## Model: linear_reg()
## 
## -- Preprocessor ----------------------------------------------------------------
## 1 Recipe Step
## 
## * step_integer()
## 
## -- Model -----------------------------------------------------------------------
## Linear Regression Model Specification (regression)
## 
## Computational engine: lm

👌 Into the bargain, a workflow can be fit/trained in much the same way a model can.

# Train the model
lm_wf_fit <- lm_wf %>% 
  fit(data = pumpkins_train)

# Print the model coefficients learned 
lm_wf_fit
## == Workflow [trained] ==========================================================
## Preprocessor: Recipe
## Model: linear_reg()
## 
## -- Preprocessor ----------------------------------------------------------------
## 1 Recipe Step
## 
## * step_integer()
## 
## -- Model -----------------------------------------------------------------------
## 
## Call:
## stats::lm(formula = ..y ~ ., data = data)
## 
## Coefficients:
## (Intercept)      package  
##      19.977        4.884

From the model output, we can see the coefficients learned during training. They represent the coefficients of the line of best fit that gives us the lowest overall error between the actual and predicted variable.

Evaluate model performance using the test set

It’s time to see how the model performed 📏! How do we do this?

Now that we’ve trained the model, we can use it to make predictions for the test_set using parsnip::predict(). Then we can compare these predictions to the actual label values to evaluate how well (or not!) the model is working.

Let’s start with making predictions for the test set then bind the columns to the test set.

# Make predictions for the test set
predictions <- lm_wf_fit %>% 
  predict(new_data = pumpkins_test)


# Bind predictions to the test set
lm_results <- pumpkins_test %>% 
  select(c(package, price)) %>% 
  bind_cols(predictions)


# Print the first ten rows of the tibble
lm_results %>% 
  slice_head(n = 10)

Yes, you have just trained a model and used it to make predictions!🔮 Is it any good, let’s evaluate the model’s performance!

In Tidymodels, we do this using yardstick::metrics()! For linear regression, let’s focus on the following metrics:

  • Root Mean Square Error (RMSE): The square root of the MSE. This yields an absolute metric in the same unit as the label (in this case, the price of a pumpkin). The smaller the value, the better the model (in a simplistic sense, it represents the average price by which the predictions are wrong!)

  • Coefficient of Determination (usually known as R-squared or R2): A relative metric in which the higher the value, the better the fit of the model. In essence, this metric represents how much of the variance between predicted and actual label values the model is able to explain.

# Evaluate performance of linear regression
metrics(data = lm_results,
        truth = price,
        estimate = .pred)

There goes the model performance. Let’s see if we can get a better indication by visualizing a scatter plot of the package and price then use the predictions made to overlay a line of best fit.

This means we’ll have to prep and bake the test set in order to encode the package column then bind this to the predictions made by our model.

# Encode package column
package_encode <- lm_pumpkins_recipe %>% 
  prep() %>% 
  bake(new_data = pumpkins_test) %>% 
  select(package)


# Bind encoded package column to the results
lm_results <- lm_results %>% 
  bind_cols(package_encode %>% 
              rename(package_integer = package)) %>% 
  relocate(package_integer, .after = package)


# Print new results data frame
lm_results %>% 
  slice_head(n = 5)
# Make a scatter plot
lm_results %>% 
  ggplot(mapping = aes(x = package_integer, y = price)) +
  geom_point(size = 1.6) +
  # Overlay a line of best fit
  geom_line(aes(y = .pred), color = "orange", size = 1.2) +
  xlab("package")
## Warning: Using `size` aesthetic for lines was deprecated in ggplot2 3.4.0.
## i Please use `linewidth` instead.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

Great! As you can see, the linear regression model does not really well generalize the relationship between a package and its corresponding price.

🎃 Congratulations, you just created a model that can help predict the price of a few varieties of pumpkins. Your holiday pumpkin patch will be beautiful. But you can probably create a better model!

5. Build a polynomial regression model

Infographic by Dasani Madipalli

Sometimes our data may not have a linear relationship, but we still want to predict an outcome. Polynomial regression can help us make predictions for more complex non-linear relationships.

Take for instance the relationship between the package and price for our pumpkins data set. While sometimes there’s a linear relationship between variables - the bigger the pumpkin in volume, the higher the price - sometimes these relationships can’t be plotted as a plane or straight line.

✅ Here are some more examples of data that could use polynomial regression

Take another look at the relationship between Variety to Price in the previous plot. Does this scatterplot seem like it should necessarily be analyzed by a straight line? Perhaps not. In this case, you can try polynomial regression.

✅ Polynomials are mathematical expressions that might consist of one or more variables and coefficients

Train a polynomial regression model using the training set

Polynomial regression creates a curved line to better fit nonlinear data.

Let’s see whether a polynomial model will perform better in making predictions. We’ll follow a somewhat similar procedure as we did before:

  • Create a recipe that specifies the preprocessing steps that should be carried out on our data to get it ready for modelling i.e: encoding predictors and computing polynomials of degree n

  • Build a model specification

  • Bundle the recipe and model specification into a workflow

  • Create a model by fitting the workflow

  • Evaluate how well the model performs on the test data

Let’s get right into it!

# Specify a recipe
poly_pumpkins_recipe <-
  recipe(price ~ package, data = pumpkins_train) %>%
  step_integer(all_predictors(), zero_based = TRUE) %>% 
  step_poly(all_predictors(), degree = 4)


# Create a model specification
poly_spec <- linear_reg() %>% 
  set_engine("lm") %>% 
  set_mode("regression")


# Bundle recipe and model spec into a workflow
poly_wf <- workflow() %>% 
  add_recipe(poly_pumpkins_recipe) %>% 
  add_model(poly_spec)


# Create a model
poly_wf_fit <- poly_wf %>% 
  fit(data = pumpkins_train)


# Print learned model coefficients
poly_wf_fit
## == Workflow [trained] ==========================================================
## Preprocessor: Recipe
## Model: linear_reg()
## 
## -- Preprocessor ----------------------------------------------------------------
## 2 Recipe Steps
## 
## * step_integer()
## * step_poly()
## 
## -- Model -----------------------------------------------------------------------
## 
## Call:
## stats::lm(formula = ..y ~ ., data = data)
## 
## Coefficients:
##    (Intercept)  package_poly_1  package_poly_2  package_poly_3  package_poly_4  
##         27.818         104.444        -113.001         -56.399           1.044

Evaluate model performance

👏👏You’ve built a polynomial model let’s make predictions on the test set!

# Make price predictions on test data
poly_results <- poly_wf_fit %>% predict(new_data = pumpkins_test) %>% 
  bind_cols(pumpkins_test %>% select(c(package, price))) %>% 
  relocate(.pred, .after = last_col())


# Print the results
poly_results %>% 
  slice_head(n = 10)

Woo-hoo , let’s evaluate how the model performed on the test_set using yardstick::metrics().

metrics(data = poly_results, truth = price, estimate = .pred)

🤩🤩 Much better performance.

The rmse decreased from about 7. to about 3. an indication that of a reduced error between the actual price and the predicted price. You can loosely interpret this as meaning that on average, incorrect predictions are wrong by around $3. The rsq increased from about 0.4 to 0.8.

All these metrics indicate that the polynomial model performs way better than the linear model. Good job!

Let’s see if we can visualize this!

# Bind encoded package column to the results
poly_results <- poly_results %>% 
  bind_cols(package_encode %>% 
              rename(package_integer = package)) %>% 
  relocate(package_integer, .after = package)


# Print new results data frame
poly_results %>% 
  slice_head(n = 5)
# Make a scatter plot
poly_results %>% 
  ggplot(mapping = aes(x = package_integer, y = price)) +
  geom_point(size = 1.6) +
  # Overlay a line of best fit
  geom_line(aes(y = .pred), color = "midnightblue", size = 1.2) +
  xlab("package")

You can see a curved line that fits your data better! 🤩

You can make this more smoother by passing a polynomial formula to geom_smooth like this:

# Make a scatter plot
poly_results %>% 
  ggplot(mapping = aes(x = package_integer, y = price)) +
  geom_point(size = 1.6) +
  # Overlay a line of best fit
  geom_smooth(method = lm, formula = y ~ poly(x, degree = 4), color = "midnightblue", size = 1.2, se = FALSE) +
  xlab("package")

Much like a smooth curve!🤩

Here’s how you would make a new prediction:

# Make a hypothetical data frame
hypo_tibble <- tibble(package = "bushel baskets")

# Make predictions using linear model
lm_pred <- lm_wf_fit %>% predict(new_data = hypo_tibble)

# Make predictions using polynomial model
poly_pred <- poly_wf_fit %>% predict(new_data = hypo_tibble)

# Return predictions in a list
list("linear model prediction" = lm_pred, 
     "polynomial model prediction" = poly_pred)
## $`linear model prediction`
## # A tibble: 1 x 1
##   .pred
##   <dbl>
## 1  34.6
## 
## $`polynomial model prediction`
## # A tibble: 1 x 1
##   .pred
##   <dbl>
## 1  46.6

The polynomial model prediction does make sense, given the scatter plots of price and package! And, if this is a better model than the previous one, looking at the same data, you need to budget for these more expensive pumpkins!

🏆 Well done! You created two regression models in one lesson. In the final section on regression, you will learn about logistic regression to determine categories.

🚀Challenge

Test several different variables in this notebook to see how correlation corresponds to model accuracy.

Post-lecture quiz

Review & Self Study

In this lesson we learned about Linear Regression. There are other important types of Regression. Read about Stepwise, Ridge, Lasso and Elasticnet techniques. A good course to study to learn more is the Stanford Statistical Learning course

If you want to learn more about how to use the amazing Tidymodels framework, please check out the following resources:

THANK YOU TO:

Allison Horst for creating the amazing illustrations that make R more welcoming and engaging. Find more illustrations at her gallery.

LS0tDQp0aXRsZTogJ0J1aWxkIGEgcmVncmVzc2lvbiBtb2RlbDogbGluZWFyIGFuZCBwb2x5bm9taWFsIHJlZ3Jlc3Npb24gbW9kZWxzJw0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIGRmX3ByaW50OiBwYWdlZA0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICBoaWdobGlnaHQ6IGJyZWV6ZWRhcmsNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQogICAgY29kZV9kb3dubG9hZDogeWVzDQotLS0NCg0KIyMgTGluZWFyIGFuZCBQb2x5bm9taWFsIFJlZ3Jlc3Npb24gZm9yIFB1bXBraW4gUHJpY2luZyAtIExlc3NvbiAzDQoNCiFbSW5mb2dyYXBoaWMgYnkgRGFzYW5pIE1hZGlwYWxsaV0oLi4vLi4vaW1hZ2VzL2xpbmVhci1wb2x5bm9taWFsLnBuZyl7d2lkdGg9IjgwMCJ9DQoNCiMjIyMgSW50cm9kdWN0aW9uDQoNClNvIGZhciB5b3UgaGF2ZSBleHBsb3JlZCB3aGF0IHJlZ3Jlc3Npb24gaXMgd2l0aCBzYW1wbGUgZGF0YSBnYXRoZXJlZCBmcm9tIHRoZSBwdW1wa2luIHByaWNpbmcgZGF0YXNldCB0aGF0IHdlIHdpbGwgdXNlIHRocm91Z2hvdXQgdGhpcyBsZXNzb24uIFlvdSBoYXZlIGFsc28gdmlzdWFsaXplZCBpdCB1c2luZyBgZ2dwbG90MmAu8J+Sqg0KDQpOb3cgeW91IGFyZSByZWFkeSB0byBkaXZlIGRlZXBlciBpbnRvIHJlZ3Jlc3Npb24gZm9yIE1MLiBJbiB0aGlzIGxlc3NvbiwgeW91IHdpbGwgbGVhcm4gbW9yZSBhYm91dCB0d28gdHlwZXMgb2YgcmVncmVzc2lvbjogKmJhc2ljIGxpbmVhciByZWdyZXNzaW9uKiBhbmQgKnBvbHlub21pYWwgcmVncmVzc2lvbiosIGFsb25nIHdpdGggc29tZSBvZiB0aGUgbWF0aCB1bmRlcmx5aW5nIHRoZXNlIHRlY2huaXF1ZXMuDQoNCj4gVGhyb3VnaG91dCB0aGlzIGN1cnJpY3VsdW0sIHdlIGFzc3VtZSBtaW5pbWFsIGtub3dsZWRnZSBvZiBtYXRoLCBhbmQgc2VlayB0byBtYWtlIGl0IGFjY2Vzc2libGUgZm9yIHN0dWRlbnRzIGNvbWluZyBmcm9tIG90aGVyIGZpZWxkcywgc28gd2F0Y2ggZm9yIG5vdGVzLCDwn6euIGNhbGxvdXRzLCBkaWFncmFtcywgYW5kIG90aGVyIGxlYXJuaW5nIHRvb2xzIHRvIGFpZCBpbiBjb21wcmVoZW5zaW9uLg0KDQojIyMjIFByZXBhcmF0aW9uDQoNCkFzIGEgcmVtaW5kZXIsIHlvdSBhcmUgbG9hZGluZyB0aGlzIGRhdGEgc28gYXMgdG8gYXNrIHF1ZXN0aW9ucyBvZiBpdC4NCg0KLSAgIFdoZW4gaXMgdGhlIGJlc3QgdGltZSB0byBidXkgcHVtcGtpbnM/DQoNCi0gICBXaGF0IHByaWNlIGNhbiBJIGV4cGVjdCBvZiBhIGNhc2Ugb2YgbWluaWF0dXJlIHB1bXBraW5zPw0KDQotICAgU2hvdWxkIEkgYnV5IHRoZW0gaW4gaGFsZi1idXNoZWwgYmFza2V0cyBvciBieSB0aGUgMSAxLzkgYnVzaGVsIGJveD8gTGV0J3Mga2VlcCBkaWdnaW5nIGludG8gdGhpcyBkYXRhLg0KDQpJbiB0aGUgcHJldmlvdXMgbGVzc29uLCB5b3UgY3JlYXRlZCBhIGB0aWJibGVgIChhIG1vZGVybiByZWltYWdpbmluZyBvZiB0aGUgZGF0YSBmcmFtZSkgYW5kIHBvcHVsYXRlZCBpdCB3aXRoIHBhcnQgb2YgdGhlIG9yaWdpbmFsIGRhdGFzZXQsIHN0YW5kYXJkaXppbmcgdGhlIHByaWNpbmcgYnkgdGhlIGJ1c2hlbC4gQnkgZG9pbmcgdGhhdCwgaG93ZXZlciwgeW91IHdlcmUgb25seSBhYmxlIHRvIGdhdGhlciBhYm91dCA0MDAgZGF0YSBwb2ludHMgYW5kIG9ubHkgZm9yIHRoZSBmYWxsIG1vbnRocy4gTWF5YmUgd2UgY2FuIGdldCBhIGxpdHRsZSBtb3JlIGRldGFpbCBhYm91dCB0aGUgbmF0dXJlIG9mIHRoZSBkYXRhIGJ5IGNsZWFuaW5nIGl0IG1vcmU/IFdlJ2xsIHNlZS4uLiDwn5W177iP4oCN4pmA77iPDQoNCkZvciB0aGlzIHRhc2ssIHdlJ2xsIHJlcXVpcmUgdGhlIGZvbGxvd2luZyBwYWNrYWdlczoNCg0KLSAgIGB0aWR5dmVyc2VgOiBUaGUgW3RpZHl2ZXJzZV0oaHR0cHM6Ly93d3cudGlkeXZlcnNlLm9yZy8pIGlzIGEgW2NvbGxlY3Rpb24gb2YgUiBwYWNrYWdlc10oaHR0cHM6Ly93d3cudGlkeXZlcnNlLm9yZy9wYWNrYWdlcykgZGVzaWduZWQgdG8gbWFrZXMgZGF0YSBzY2llbmNlIGZhc3RlciwgZWFzaWVyIGFuZCBtb3JlIGZ1biENCg0KLSAgIGB0aWR5bW9kZWxzYDogVGhlIFt0aWR5bW9kZWxzXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy8pIGZyYW1ld29yayBpcyBhIFtjb2xsZWN0aW9uIG9mIHBhY2thZ2VzXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy9wYWNrYWdlcy8pIGZvciBtb2RlbGluZyBhbmQgbWFjaGluZSBsZWFybmluZy4NCg0KLSAgIGBqYW5pdG9yYDogVGhlIFtqYW5pdG9yIHBhY2thZ2VdKGh0dHBzOi8vZ2l0aHViLmNvbS9zZmlya2UvamFuaXRvcikgcHJvdmlkZXMgc2ltcGxlIGxpdHRsZSB0b29scyBmb3IgZXhhbWluaW5nIGFuZCBjbGVhbmluZyBkaXJ0eSBkYXRhLg0KDQotICAgYGNvcnJwbG90YDogVGhlIFtjb3JycGxvdCBwYWNrYWdlXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvY29ycnBsb3QvdmlnbmV0dGVzL2NvcnJwbG90LWludHJvLmh0bWwpIHByb3ZpZGVzIGEgdmlzdWFsIGV4cGxvcmF0b3J5IHRvb2wgb24gY29ycmVsYXRpb24gbWF0cml4IHRoYXQgc3VwcG9ydHMgYXV0b21hdGljIHZhcmlhYmxlIHJlb3JkZXJpbmcgdG8gaGVscCBkZXRlY3QgaGlkZGVuIHBhdHRlcm5zIGFtb25nIHZhcmlhYmxlcy4NCg0KWW91IGNhbiBoYXZlIHRoZW0gaW5zdGFsbGVkIGFzOg0KDQpgaW5zdGFsbC5wYWNrYWdlcyhjKCJ0aWR5dmVyc2UiLCAidGlkeW1vZGVscyIsICJqYW5pdG9yIiwgImNvcnJwbG90IikpYA0KDQpUaGUgc2NyaXB0IGJlbG93IGNoZWNrcyB3aGV0aGVyIHlvdSBoYXZlIHRoZSBwYWNrYWdlcyByZXF1aXJlZCB0byBjb21wbGV0ZSB0aGlzIG1vZHVsZSBhbmQgaW5zdGFsbHMgdGhlbSBmb3IgeW91IGluIGNhc2UgdGhleSBhcmUgbWlzc2luZy4NCg0KYGBge3IsIG1lc3NhZ2U9Riwgd2FybmluZz1GfQ0Kc3VwcHJlc3NXYXJuaW5ncyhpZiAoIXJlcXVpcmUoInBhY21hbiIpKSBpbnN0YWxsLnBhY2thZ2VzKCJwYWNtYW4iKSkNCg0KcGFjbWFuOjpwX2xvYWQodGlkeXZlcnNlLCB0aWR5bW9kZWxzLCBqYW5pdG9yLCBjb3JycGxvdCkNCmBgYA0KDQpXZSdsbCBsYXRlciBsb2FkIHRoZXNlIGF3ZXNvbWUgcGFja2FnZXMgYW5kIG1ha2UgdGhlbSBhdmFpbGFibGUgaW4gb3VyIGN1cnJlbnQgUiBzZXNzaW9uLiAoVGhpcyBpcyBmb3IgbWVyZSBpbGx1c3RyYXRpb24sIGBwYWNtYW46OnBfbG9hZCgpYCBhbHJlYWR5IGRpZCB0aGF0IGZvciB5b3UpDQoNCiMjIDEuIEEgbGluZWFyIHJlZ3Jlc3Npb24gbGluZQ0KDQpBcyB5b3UgbGVhcm5lZCBpbiBMZXNzb24gMSwgdGhlIGdvYWwgb2YgYSBsaW5lYXIgcmVncmVzc2lvbiBleGVyY2lzZSBpcyB0byBiZSBhYmxlIHRvIHBsb3QgYSAqbGluZSogKm9mKiAqYmVzdCBmaXQqIHRvOg0KDQotICAgKipTaG93IHZhcmlhYmxlIHJlbGF0aW9uc2hpcHMqKi4gU2hvdyB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gdmFyaWFibGVzDQoNCi0gICAqKk1ha2UgcHJlZGljdGlvbnMqKi4gTWFrZSBhY2N1cmF0ZSBwcmVkaWN0aW9ucyBvbiB3aGVyZSBhIG5ldyBkYXRhIHBvaW50IHdvdWxkIGZhbGwgaW4gcmVsYXRpb25zaGlwIHRvIHRoYXQgbGluZS4NCg0KVG8gZHJhdyB0aGlzIHR5cGUgb2YgbGluZSwgd2UgdXNlIGEgc3RhdGlzdGljYWwgdGVjaG5pcXVlIGNhbGxlZCAqKkxlYXN0LVNxdWFyZXMgUmVncmVzc2lvbioqLiBUaGUgdGVybSBgbGVhc3Qtc3F1YXJlc2AgbWVhbnMgdGhhdCBhbGwgdGhlIGRhdGEgcG9pbnRzIHN1cnJvdW5kaW5nIHRoZSByZWdyZXNzaW9uIGxpbmUgYXJlIHNxdWFyZWQgYW5kIHRoZW4gYWRkZWQgdXAuIElkZWFsbHksIHRoYXQgZmluYWwgc3VtIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLCBiZWNhdXNlIHdlIHdhbnQgYSBsb3cgbnVtYmVyIG9mIGVycm9ycywgb3IgYGxlYXN0LXNxdWFyZXNgLiBBcyBzdWNoLCB0aGUgbGluZSBvZiBiZXN0IGZpdCBpcyB0aGUgbGluZSB0aGF0IGdpdmVzIHVzIHRoZSBsb3dlc3QgdmFsdWUgZm9yIHRoZSBzdW0gb2YgdGhlIHNxdWFyZWQgZXJyb3JzIC0gaGVuY2UgdGhlIG5hbWUgKmxlYXN0IHNxdWFyZXMgcmVncmVzc2lvbiouDQoNCldlIGRvIHNvIHNpbmNlIHdlIHdhbnQgdG8gbW9kZWwgYSBsaW5lIHRoYXQgaGFzIHRoZSBsZWFzdCBjdW11bGF0aXZlIGRpc3RhbmNlIGZyb20gYWxsIG9mIG91ciBkYXRhIHBvaW50cy4gV2UgYWxzbyBzcXVhcmUgdGhlIHRlcm1zIGJlZm9yZSBhZGRpbmcgdGhlbSBzaW5jZSB3ZSBhcmUgY29uY2VybmVkIHdpdGggaXRzIG1hZ25pdHVkZSByYXRoZXIgdGhhbiBpdHMgZGlyZWN0aW9uLg0KDQo+ICoq8J+nriBTaG93IG1lIHRoZSBtYXRoKioNCj4NCj4gVGhpcyBsaW5lLCBjYWxsZWQgdGhlICpsaW5lIG9mIGJlc3QgZml0KiBjYW4gYmUgZXhwcmVzc2VkIGJ5IFthbiBlcXVhdGlvbl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvU2ltcGxlX2xpbmVhcl9yZWdyZXNzaW9uKToNCj4NCj4gICAgIFkgPSBhICsgYlgNCj4NCj4gYFhgIGlzIHRoZSAnYGV4cGxhbmF0b3J5IHZhcmlhYmxlYCBvciBgcHJlZGljdG9yYCcuIGBZYCBpcyB0aGUgJ2BkZXBlbmRlbnQgdmFyaWFibGVgIG9yIGBvdXRjb21lYCcuIFRoZSBzbG9wZSBvZiB0aGUgbGluZSBpcyBgYmAgYW5kIGBhYCBpcyB0aGUgeS1pbnRlcmNlcHQsIHdoaWNoIHJlZmVycyB0byB0aGUgdmFsdWUgb2YgYFlgIHdoZW4gYFggPSAwYC4NCj4NCj4gIVtJbmZvZ3JhcGhpYyBieSBKZW4gTG9vcGVyXSguLi8uLi9pbWFnZXMvc2xvcGUucG5nKXt3aWR0aD0iNDAwIn0NCj4NCj4gRmlyc3QsIGNhbGN1bGF0ZSB0aGUgc2xvcGUgYGJgLg0KPg0KPiBJbiBvdGhlciB3b3JkcywgYW5kIHJlZmVycmluZyB0byBvdXIgcHVtcGtpbiBkYXRhJ3Mgb3JpZ2luYWwgcXVlc3Rpb246ICJwcmVkaWN0IHRoZSBwcmljZSBvZiBhIHB1bXBraW4gcGVyIGJ1c2hlbCBieSBtb250aCIsIGBYYCB3b3VsZCByZWZlciB0byB0aGUgcHJpY2UgYW5kIGBZYCB3b3VsZCByZWZlciB0byB0aGUgbW9udGggb2Ygc2FsZS4NCj4NCiFbSW5mb2dyYXBoaWMgYnkgSmVuIExvb3Blcl0oLi4vLi4vaW1hZ2VzL2NhbGN1bGF0aW9uLnBuZykNCg0KPiBDYWxjdWxhdGUgdGhlIHZhbHVlIG9mIFkuIElmIHlvdSdyZSBwYXlpbmcgYXJvdW5kIFwkNCwgaXQgbXVzdCBiZSBBcHJpbCENCj4NCj4gVGhlIG1hdGggdGhhdCBjYWxjdWxhdGVzIHRoZSBsaW5lIG11c3QgZGVtb25zdHJhdGUgdGhlIHNsb3BlIG9mIHRoZSBsaW5lLCB3aGljaCBpcyBhbHNvIGRlcGVuZGVudCBvbiB0aGUgaW50ZXJjZXB0LCBvciB3aGVyZSBgWWAgaXMgc2l0dWF0ZWQgd2hlbiBgWCA9IDBgLg0KPg0KPiBZb3UgY2FuIG9ic2VydmUgdGhlIG1ldGhvZCBvZiBjYWxjdWxhdGlvbiBmb3IgdGhlc2UgdmFsdWVzIG9uIHRoZSBbTWF0aCBpcyBGdW5dKGh0dHBzOi8vd3d3Lm1hdGhzaXNmdW4uY29tL2RhdGEvbGVhc3Qtc3F1YXJlcy1yZWdyZXNzaW9uLmh0bWwpIHdlYiBzaXRlLiBBbHNvIHZpc2l0IFt0aGlzIExlYXN0LXNxdWFyZXMgY2FsY3VsYXRvcl0oaHR0cHM6Ly93d3cubWF0aHNpc2Z1bi5jb20vZGF0YS9sZWFzdC1zcXVhcmVzLWNhbGN1bGF0b3IuaHRtbCkgdG8gd2F0Y2ggaG93IHRoZSBudW1iZXJzJyB2YWx1ZXMgaW1wYWN0IHRoZSBsaW5lLg0KDQpOb3Qgc28gc2NhcnksIHJpZ2h0PyDwn6STDQoNCiMjIyMgQ29ycmVsYXRpb24NCg0KT25lIG1vcmUgdGVybSB0byB1bmRlcnN0YW5kIGlzIHRoZSAqKkNvcnJlbGF0aW9uIENvZWZmaWNpZW50KiogYmV0d2VlbiBnaXZlbiBYIGFuZCBZIHZhcmlhYmxlcy4gVXNpbmcgYSBzY2F0dGVycGxvdCwgeW91IGNhbiBxdWlja2x5IHZpc3VhbGl6ZSB0aGlzIGNvZWZmaWNpZW50LiBBIHBsb3Qgd2l0aCBkYXRhcG9pbnRzIHNjYXR0ZXJlZCBpbiBhIG5lYXQgbGluZSBoYXZlIGhpZ2ggY29ycmVsYXRpb24sIGJ1dCBhIHBsb3Qgd2l0aCBkYXRhcG9pbnRzIHNjYXR0ZXJlZCBldmVyeXdoZXJlIGJldHdlZW4gWCBhbmQgWSBoYXZlIGEgbG93IGNvcnJlbGF0aW9uLg0KDQpBIGdvb2QgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgd2lsbCBiZSBvbmUgdGhhdCBoYXMgYSBoaWdoIChuZWFyZXIgdG8gMSB0aGFuIDApIENvcnJlbGF0aW9uIENvZWZmaWNpZW50IHVzaW5nIHRoZSBMZWFzdC1TcXVhcmVzIFJlZ3Jlc3Npb24gbWV0aG9kIHdpdGggYSBsaW5lIG9mIHJlZ3Jlc3Npb24uDQoNCiMjICoqMi4gQSBkYW5jZSB3aXRoIGRhdGE6IGNyZWF0aW5nIGEgZGF0YSBmcmFtZSB0aGF0IHdpbGwgYmUgdXNlZCBmb3IgbW9kZWxsaW5nKioNCg0KIVtBcnR3b3JrIGJ5IFxAYWxsaXNvbl9ob3JzdF0oLi4vLi4vaW1hZ2VzL2phbml0b3IuanBnKXt3aWR0aD0iNzAwIn0NCg0KTG9hZCB1cCByZXF1aXJlZCBsaWJyYXJpZXMgYW5kIGRhdGFzZXQuIENvbnZlcnQgdGhlIGRhdGEgdG8gYSBkYXRhIGZyYW1lIGNvbnRhaW5pbmcgYSBzdWJzZXQgb2YgdGhlIGRhdGE6DQoNCi0gICBPbmx5IGdldCBwdW1wa2lucyBwcmljZWQgYnkgdGhlIGJ1c2hlbA0KDQotICAgQ29udmVydCB0aGUgZGF0ZSB0byBhIG1vbnRoDQoNCi0gICBDYWxjdWxhdGUgdGhlIHByaWNlIHRvIGJlIGFuIGF2ZXJhZ2Ugb2YgaGlnaCBhbmQgbG93IHByaWNlcw0KDQotICAgQ29udmVydCB0aGUgcHJpY2UgdG8gcmVmbGVjdCB0aGUgcHJpY2luZyBieSBidXNoZWwgcXVhbnRpdHkNCg0KPiBXZSBjb3ZlcmVkIHRoZXNlIHN0ZXBzIGluIHRoZSBbcHJldmlvdXMgbGVzc29uXShodHRwczovL2dpdGh1Yi5jb20vbWljcm9zb2Z0L01MLUZvci1CZWdpbm5lcnMvYmxvYi9tYWluLzItUmVncmVzc2lvbi8yLURhdGEvc29sdXRpb24vbGVzc29uXzIuaHRtbCkuDQoNCmBgYHtyIGxvYWRfdGlkeV92ZXJzZV9tb2RlbHMsIG1lc3NhZ2U9Riwgd2FybmluZz1GfQ0KIyBMb2FkIHRoZSBjb3JlIFRpZHl2ZXJzZSBwYWNrYWdlcw0KbGlicmFyeSh0aWR5dmVyc2UpDQpsaWJyYXJ5KGx1YnJpZGF0ZSkNCg0KIyBJbXBvcnQgdGhlIHB1bXBraW5zIGRhdGENCnB1bXBraW5zIDwtIHJlYWRfY3N2KGZpbGUgPSAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21pY3Jvc29mdC9NTC1Gb3ItQmVnaW5uZXJzL21haW4vMi1SZWdyZXNzaW9uL2RhdGEvVVMtcHVtcGtpbnMuY3N2IikNCg0KDQojIEdldCBhIGdsaW1wc2UgYW5kIGRpbWVuc2lvbnMgb2YgdGhlIGRhdGENCmdsaW1wc2UocHVtcGtpbnMpDQoNCg0KIyBQcmludCB0aGUgZmlyc3QgNTAgcm93cyBvZiB0aGUgZGF0YSBzZXQNCnB1bXBraW5zICU+JSANCiAgc2xpY2VfaGVhZChuID0gNSkNCg0KDQpgYGANCg0KSW4gdGhlIHNwaXJpdCBvZiBzaGVlciBhZHZlbnR1cmUsIGxldCdzIGV4cGxvcmUgdGhlIFtgamFuaXRvciBwYWNrYWdlYF0oZ2l0aHViLmNvbS9zZmlya2UvamFuaXRvcikgdGhhdCBwcm92aWRlcyBzaW1wbGUgZnVuY3Rpb25zIGZvciBleGFtaW5pbmcgYW5kIGNsZWFuaW5nIGRpcnR5IGRhdGEuIEZvciBpbnN0YW5jZSwgbGV0J3MgdGFrZSBhIGxvb2sgYXQgdGhlIGNvbHVtbiBuYW1lcyBmb3Igb3VyIGRhdGE6DQoNCmBgYHtyIGNvbF9uYW1lc30NCiMgUmV0dXJuIGNvbHVtbiBuYW1lcw0KcHVtcGtpbnMgJT4lIA0KICBuYW1lcygpDQoNCmBgYA0KDQrwn6SUIFdlIGNhbiBkbyBiZXR0ZXIuIExldCdzIG1ha2UgdGhlc2UgY29sdW1uIG5hbWVzIGBmcmllbmRSYCBieSBjb252ZXJ0aW5nIHRoZW0gdG8gdGhlIFtzbmFrZV9jYXNlXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9TbmFrZV9jYXNlKSBjb252ZW50aW9uIHVzaW5nIGBqYW5pdG9yOjpjbGVhbl9uYW1lc2AuIFRvIGZpbmQgb3V0IG1vcmUgYWJvdXQgdGhpcyBmdW5jdGlvbjogYD9jbGVhbl9uYW1lc2ANCg0KYGBge3IgZnJpZW5kUn0NCiMgQ2xlYW4gbmFtZXMgdG8gdGhlIHNuYWtlX2Nhc2UgY29udmVudGlvbg0KcHVtcGtpbnMgPC0gcHVtcGtpbnMgJT4lIA0KICBjbGVhbl9uYW1lcyhjYXNlID0gInNuYWtlIikNCg0KIyBSZXR1cm4gY29sdW1uIG5hbWVzDQpwdW1wa2lucyAlPiUgDQogIG5hbWVzKCkNCg0KYGBgDQoNCk11Y2ggdGlkeVIg8J+nuSEgTm93LCBhIGRhbmNlIHdpdGggdGhlIGRhdGEgdXNpbmcgYGRwbHlyYCBhcyBpbiB0aGUgcHJldmlvdXMgbGVzc29uISDwn5KDDQoNCmBgYHtyIHByZXBfZGF0YSwgbWVzc2FnZT1GLCB3YXJuaW5nPUZ9DQojIFNlbGVjdCBkZXNpcmVkIGNvbHVtbnMNCnB1bXBraW5zIDwtIHB1bXBraW5zICU+JSANCiAgc2VsZWN0KHZhcmlldHksIGNpdHlfbmFtZSwgcGFja2FnZSwgbG93X3ByaWNlLCBoaWdoX3ByaWNlLCBkYXRlKQ0KDQoNCg0KIyBFeHRyYWN0IHRoZSBtb250aCBmcm9tIHRoZSBkYXRlcyB0byBhIG5ldyBjb2x1bW4NCnB1bXBraW5zIDwtIHB1bXBraW5zICU+JQ0KICBtdXRhdGUoZGF0ZSA9IG1keShkYXRlKSwNCiAgICAgICAgIG1vbnRoID0gbW9udGgoZGF0ZSkpICU+JSANCiAgc2VsZWN0KC1kYXRlKQ0KDQoNCg0KIyBDcmVhdGUgYSBuZXcgY29sdW1uIGZvciBhdmVyYWdlIFByaWNlDQpwdW1wa2lucyA8LSBwdW1wa2lucyAlPiUgDQogIG11dGF0ZShwcmljZSA9IChsb3dfcHJpY2UgKyBoaWdoX3ByaWNlKS8yKQ0KDQoNCiMgUmV0YWluIG9ubHkgcHVtcGtpbnMgd2l0aCB0aGUgc3RyaW5nICJidXNoZWwiDQpuZXdfcHVtcGtpbnMgPC0gcHVtcGtpbnMgJT4lIA0KICBmaWx0ZXIoc3RyX2RldGVjdChzdHJpbmcgPSBwYWNrYWdlLCBwYXR0ZXJuID0gImJ1c2hlbCIpKQ0KDQoNCiMgTm9ybWFsaXplIHRoZSBwcmljaW5nIHNvIHRoYXQgeW91IHNob3cgdGhlIHByaWNpbmcgcGVyIGJ1c2hlbCwgbm90IHBlciAxIDEvOSBvciAxLzIgYnVzaGVsDQpuZXdfcHVtcGtpbnMgPC0gbmV3X3B1bXBraW5zICU+JSANCiAgbXV0YXRlKHByaWNlID0gY2FzZV93aGVuKA0KICAgIHN0cl9kZXRlY3QocGFja2FnZSwgIjEgMS85IikgfiBwcmljZS8oMS4xKSwNCiAgICBzdHJfZGV0ZWN0KHBhY2thZ2UsICIxLzIiKSB+IHByaWNlKjIsDQogICAgVFJVRSB+IHByaWNlKSkNCg0KIyBSZWxvY2F0ZSBjb2x1bW4gcG9zaXRpb25zDQpuZXdfcHVtcGtpbnMgPC0gbmV3X3B1bXBraW5zICU+JSANCiAgcmVsb2NhdGUobW9udGgsIC5iZWZvcmUgPSB2YXJpZXR5KQ0KDQoNCiMgRGlzcGxheSB0aGUgZmlyc3QgNSByb3dzDQpuZXdfcHVtcGtpbnMgJT4lIA0KICBzbGljZV9oZWFkKG4gPSA1KQ0KYGBgDQoNCkdvb2Qgam9iIfCfkYwgWW91IG5vdyBoYXZlIGEgY2xlYW4sIHRpZHkgZGF0YSBzZXQgb24gd2hpY2ggeW91IGNhbiBidWlsZCB5b3VyIG5ldyByZWdyZXNzaW9uIG1vZGVsIQ0KDQpNaW5kIGEgc2NhdHRlciBwbG90Pw0KDQpgYGB7ciBzY2F0dGVyX3ByaWNlX21vbnRofQ0KIyBTZXQgdGhlbWUNCnRoZW1lX3NldCh0aGVtZV9saWdodCgpKQ0KDQojIE1ha2UgYSBzY2F0dGVyIHBsb3Qgb2YgbW9udGggYW5kIHByaWNlDQpuZXdfcHVtcGtpbnMgJT4lIA0KICBnZ3Bsb3QobWFwcGluZyA9IGFlcyh4ID0gbW9udGgsIHkgPSBwcmljZSkpICsNCiAgZ2VvbV9wb2ludChzaXplID0gMS42KQ0KDQpgYGANCg0KQSBzY2F0dGVyIHBsb3QgcmVtaW5kcyB1cyB0aGF0IHdlIG9ubHkgaGF2ZSBtb250aCBkYXRhIGZyb20gQXVndXN0IHRocm91Z2ggRGVjZW1iZXIuIFdlIHByb2JhYmx5IG5lZWQgbW9yZSBkYXRhIHRvIGJlIGFibGUgdG8gZHJhdyBjb25jbHVzaW9ucyBpbiBhIGxpbmVhciBmYXNoaW9uLg0KDQpMZXQncyB0YWtlIGEgbG9vayBhdCBvdXIgbW9kZWxsaW5nIGRhdGEgYWdhaW46DQoNCmBgYHtyIG1vZGVsbGluZyBkYXRhfQ0KIyBEaXNwbGF5IGZpcnN0IDUgcm93cw0KbmV3X3B1bXBraW5zICU+JSANCiAgc2xpY2VfaGVhZChuID0gNSkNCg0KYGBgDQoNCldoYXQgaWYgd2Ugd2FudGVkIHRvIHByZWRpY3QgdGhlIGBwcmljZWAgb2YgYSBwdW1wa2luIGJhc2VkIG9uIHRoZSBgY2l0eWAgb3IgYHBhY2thZ2VgIGNvbHVtbnMgd2hpY2ggYXJlIG9mIHR5cGUgY2hhcmFjdGVyPyBPciBldmVuIG1vcmUgc2ltcGx5LCBob3cgY291bGQgd2UgZmluZCB0aGUgY29ycmVsYXRpb24gKHdoaWNoIHJlcXVpcmVzIGJvdGggb2YgaXRzIGlucHV0cyB0byBiZSBudW1lcmljKSBiZXR3ZWVuLCBzYXksIGBwYWNrYWdlYCBhbmQgYHByaWNlYD8g8J+kt/CfpLcNCg0KTWFjaGluZSBsZWFybmluZyBtb2RlbHMgd29yayBiZXN0IHdpdGggbnVtZXJpYyBmZWF0dXJlcyByYXRoZXIgdGhhbiB0ZXh0IHZhbHVlcywgc28geW91IGdlbmVyYWxseSBuZWVkIHRvIGNvbnZlcnQgY2F0ZWdvcmljYWwgZmVhdHVyZXMgaW50byBudW1lcmljIHJlcHJlc2VudGF0aW9ucy4NCg0KVGhpcyBtZWFucyB0aGF0IHdlIGhhdmUgdG8gZmluZCBhIHdheSB0byByZWZvcm1hdCBvdXIgcHJlZGljdG9ycyB0byBtYWtlIHRoZW0gZWFzaWVyIGZvciBhIG1vZGVsIHRvIHVzZSBlZmZlY3RpdmVseSwgYSBwcm9jZXNzIGtub3duIGFzIGBmZWF0dXJlIGVuZ2luZWVyaW5nYC4NCg0KIyMgMy4gUHJlcHJvY2Vzc2luZyBkYXRhIGZvciBtb2RlbGxpbmcgd2l0aCByZWNpcGVzIPCfkanigI3wn42z8J+RqOKAjfCfjbMNCg0KQWN0aXZpdGllcyB0aGF0IHJlZm9ybWF0IHByZWRpY3RvciB2YWx1ZXMgdG8gbWFrZSB0aGVtIGVhc2llciBmb3IgYSBtb2RlbCB0byB1c2UgZWZmZWN0aXZlbHkgaGFzIGJlZW4gdGVybWVkIGBmZWF0dXJlIGVuZ2luZWVyaW5nYC4NCg0KRGlmZmVyZW50IG1vZGVscyBoYXZlIGRpZmZlcmVudCBwcmVwcm9jZXNzaW5nIHJlcXVpcmVtZW50cy4gRm9yIGluc3RhbmNlLCBsZWFzdCBzcXVhcmVzIHJlcXVpcmVzIGBlbmNvZGluZyBjYXRlZ29yaWNhbCB2YXJpYWJsZXNgIHN1Y2ggYXMgbW9udGgsIHZhcmlldHkgYW5kIGNpdHlfbmFtZS4gVGhpcyBzaW1wbHkgaW52b2x2ZXMgYHRyYW5zbGF0aW5nYCBhIGNvbHVtbiB3aXRoIGBjYXRlZ29yaWNhbCB2YWx1ZXNgIGludG8gb25lIG9yIG1vcmUgYG51bWVyaWMgY29sdW1uc2AgdGhhdCB0YWtlIHRoZSBwbGFjZSBvZiB0aGUgb3JpZ2luYWwuDQoNCkZvciBleGFtcGxlLCBzdXBwb3NlIHlvdXIgZGF0YSBpbmNsdWRlcyB0aGUgZm9sbG93aW5nIGNhdGVnb3JpY2FsIGZlYXR1cmU6DQoNCnwgIGNpdHkgICB8DQp8Oi0tLS0tLS06fA0KfCBEZW52ZXIgIHwNCnwgTmFpcm9iaSB8DQp8ICBUb2t5byAgfA0KDQpZb3UgY2FuIGFwcGx5ICpvcmRpbmFsIGVuY29kaW5nKiB0byBzdWJzdGl0dXRlIGEgdW5pcXVlIGludGVnZXIgdmFsdWUgZm9yIGVhY2ggY2F0ZWdvcnksIGxpa2UgdGhpczoNCg0KfCBjaXR5IHwNCnw6LS0tLTp8DQp8ICAwICAgfA0KfCAgMSAgIHwNCnwgIDIgICB8DQoNCkFuZCB0aGF0J3Mgd2hhdCB3ZSdsbCBkbyB0byBvdXIgZGF0YSENCg0KSW4gdGhpcyBzZWN0aW9uLCB3ZSdsbCBleHBsb3JlIGFub3RoZXIgYW1hemluZyBUaWR5bW9kZWxzIHBhY2thZ2U6IFtyZWNpcGVzXShodHRwczovL3RpZHltb2RlbHMuZ2l0aHViLmlvL3JlY2lwZXMvKSAtIHdoaWNoIGlzIGRlc2lnbmVkIHRvIGhlbHAgeW91IHByZXByb2Nlc3MgeW91ciBkYXRhICoqYmVmb3JlKiogdHJhaW5pbmcgeW91ciBtb2RlbC4gQXQgaXRzIGNvcmUsIGEgcmVjaXBlIGlzIGFuIG9iamVjdCB0aGF0IGRlZmluZXMgd2hhdCBzdGVwcyBzaG91bGQgYmUgYXBwbGllZCB0byBhIGRhdGEgc2V0IGluIG9yZGVyIHRvIGdldCBpdCByZWFkeSBmb3IgbW9kZWxsaW5nLg0KDQpOb3csIGxldCdzIGNyZWF0ZSBhIHJlY2lwZSB0aGF0IHByZXBhcmVzIG91ciBkYXRhIGZvciBtb2RlbGxpbmcgYnkgc3Vic3RpdHV0aW5nIGEgdW5pcXVlIGludGVnZXIgZm9yIGFsbCB0aGUgb2JzZXJ2YXRpb25zIGluIHRoZSBwcmVkaWN0b3IgY29sdW1uczoNCg0KYGBge3IgcHVtcGtpbnNfcmVjaXBlfQ0KIyBTcGVjaWZ5IGEgcmVjaXBlDQpwdW1wa2luc19yZWNpcGUgPC0gcmVjaXBlKHByaWNlIH4gLiwgZGF0YSA9IG5ld19wdW1wa2lucykgJT4lIA0KICBzdGVwX2ludGVnZXIoYWxsX3ByZWRpY3RvcnMoKSwgemVyb19iYXNlZCA9IFRSVUUpDQoNCg0KIyBQcmludCBvdXQgdGhlIHJlY2lwZQ0KcHVtcGtpbnNfcmVjaXBlDQoNCmBgYA0KDQpBd2Vzb21lISDwn5GPIFdlIGp1c3QgY3JlYXRlZCBvdXIgZmlyc3QgcmVjaXBlIHRoYXQgc3BlY2lmaWVzIGFuIG91dGNvbWUgKHByaWNlKSBhbmQgaXRzIGNvcnJlc3BvbmRpbmcgcHJlZGljdG9ycyBhbmQgdGhhdCBhbGwgdGhlIHByZWRpY3RvciBjb2x1bW5zIHNob3VsZCBiZSBlbmNvZGVkIGludG8gYSBzZXQgb2YgaW50ZWdlcnMg8J+ZjCEgTGV0J3MgcXVpY2tseSBicmVhayBpdCBkb3duOg0KDQotICAgVGhlIGNhbGwgdG8gYHJlY2lwZSgpYCB3aXRoIGEgZm9ybXVsYSB0ZWxscyB0aGUgcmVjaXBlIHRoZSAqcm9sZXMqIG9mIHRoZSB2YXJpYWJsZXMgdXNpbmcgYG5ld19wdW1wa2luc2AgZGF0YSBhcyB0aGUgcmVmZXJlbmNlLiBGb3IgaW5zdGFuY2UgdGhlIGBwcmljZWAgY29sdW1uIGhhcyBiZWVuIGFzc2lnbmVkIGFuIGBvdXRjb21lYCByb2xlIHdoaWxlIHRoZSByZXN0IG9mIHRoZSBjb2x1bW5zIGhhdmUgYmVlbiBhc3NpZ25lZCBhIGBwcmVkaWN0b3JgIHJvbGUuDQoNCi0gICBgc3RlcF9pbnRlZ2VyKGFsbF9wcmVkaWN0b3JzKCksIHplcm9fYmFzZWQgPSBUUlVFKWAgc3BlY2lmaWVzIHRoYXQgYWxsIHRoZSBwcmVkaWN0b3JzIHNob3VsZCBiZSBjb252ZXJ0ZWQgaW50byBhIHNldCBvZiBpbnRlZ2VycyB3aXRoIHRoZSBudW1iZXJpbmcgc3RhcnRpbmcgYXQgMC4NCg0KV2UgYXJlIHN1cmUgeW91IG1heSBiZSBoYXZpbmcgdGhvdWdodHMgc3VjaCBhczogIlRoaXMgaXMgc28gY29vbCEhIEJ1dCB3aGF0IGlmIEkgbmVlZGVkIHRvIGNvbmZpcm0gdGhhdCB0aGUgcmVjaXBlcyBhcmUgZG9pbmcgZXhhY3RseSB3aGF0IEkgZXhwZWN0IHRoZW0gdG8gZG8/IPCfpJQiDQoNClRoYXQncyBhbiBhd2Vzb21lIHRob3VnaHQhIFlvdSBzZWUsIG9uY2UgeW91ciByZWNpcGUgaXMgZGVmaW5lZCwgeW91IGNhbiBlc3RpbWF0ZSB0aGUgcGFyYW1ldGVycyByZXF1aXJlZCB0byBhY3R1YWxseSBwcmVwcm9jZXNzIHRoZSBkYXRhLCBhbmQgdGhlbiBleHRyYWN0IHRoZSBwcm9jZXNzZWQgZGF0YS4gWW91IGRvbid0IHR5cGljYWxseSBuZWVkIHRvIGRvIHRoaXMgd2hlbiB5b3UgdXNlIFRpZHltb2RlbHMgKHdlJ2xsIHNlZSB0aGUgbm9ybWFsIGNvbnZlbnRpb24gaW4ganVzdCBhIG1pbnV0ZS1cPiBgd29ya2Zsb3dzYCkgYnV0IGl0IGNhbiBjb21lIGluIGhhbmR5IHdoZW4geW91IHdhbnQgdG8gZG8gc29tZSBraW5kIG9mIHNhbml0eSBjaGVjayBmb3IgY29uZmlybWluZyB0aGF0IHJlY2lwZXMgYXJlIGRvaW5nIHdoYXQgeW91IGV4cGVjdC4NCg0KRm9yIHRoYXQsIHlvdSdsbCBuZWVkIHR3byBtb3JlIHZlcmJzOiBgcHJlcCgpYCBhbmQgYGJha2UoKWAgYW5kIGFzIGFsd2F5cywgb3VyIGxpdHRsZSBSIGZyaWVuZHMgYnkgW2BBbGxpc29uIEhvcnN0YF0oaHR0cHM6Ly9naXRodWIuY29tL2FsbGlzb25ob3JzdC9zdGF0cy1pbGx1c3RyYXRpb25zKSBoZWxwIHlvdSBpbiB1bmRlcnN0YW5kaW5nIHRoaXMgYmV0dGVyIQ0KDQohW0FydHdvcmsgYnkgXEBhbGxpc29uX2hvcnN0XSguLi8uLi9pbWFnZXMvcmVjaXBlcy5wbmcpe3dpZHRoPSI1NTAifQ0KDQpbYHByZXAoKWBdKGh0dHBzOi8vcmVjaXBlcy50aWR5bW9kZWxzLm9yZy9yZWZlcmVuY2UvcHJlcC5odG1sKTogZXN0aW1hdGVzIHRoZSByZXF1aXJlZCBwYXJhbWV0ZXJzIGZyb20gYSB0cmFpbmluZyBzZXQgdGhhdCBjYW4gYmUgbGF0ZXIgYXBwbGllZCB0byBvdGhlciBkYXRhIHNldHMuIEZvciBpbnN0YW5jZSwgZm9yIGEgZ2l2ZW4gcHJlZGljdG9yIGNvbHVtbiwgd2hhdCBvYnNlcnZhdGlvbiB3aWxsIGJlIGFzc2lnbmVkIGludGVnZXIgMCBvciAxIG9yIDIgZXRjDQoNCltgYmFrZSgpYF0oaHR0cHM6Ly9yZWNpcGVzLnRpZHltb2RlbHMub3JnL3JlZmVyZW5jZS9iYWtlLmh0bWwpOiB0YWtlcyBhIHByZXBwZWQgcmVjaXBlIGFuZCBhcHBsaWVzIHRoZSBvcGVyYXRpb25zIHRvIGFueSBkYXRhIHNldC4NCg0KVGhhdCBzYWlkLCBsZXRzIHByZXAgYW5kIGJha2Ugb3VyIHJlY2lwZXMgdG8gcmVhbGx5IGNvbmZpcm0gdGhhdCB1bmRlciB0aGUgaG9vZCwgdGhlIHByZWRpY3RvciBjb2x1bW5zIHdpbGwgYmUgZmlyc3QgZW5jb2RlZCBiZWZvcmUgYSBtb2RlbCBpcyBmaXQuDQoNCmBgYHtyIHByZXBfYmFrZX0NCiMgUHJlcCB0aGUgcmVjaXBlDQpwdW1wa2luc19wcmVwIDwtIHByZXAocHVtcGtpbnNfcmVjaXBlKQ0KDQojIEJha2UgdGhlIHJlY2lwZSB0byBleHRyYWN0IGEgcHJlcHJvY2Vzc2VkIG5ld19wdW1wa2lucyBkYXRhDQpiYWtlZF9wdW1wa2lucyA8LSBiYWtlKHB1bXBraW5zX3ByZXAsIG5ld19kYXRhID0gTlVMTCkNCg0KIyBQcmludCBvdXQgdGhlIGJha2VkIGRhdGEgc2V0DQpiYWtlZF9wdW1wa2lucyAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDEwKQ0KYGBgDQoNCldvby1ob28h8J+lsyBUaGUgcHJvY2Vzc2VkIGRhdGEgYGJha2VkX3B1bXBraW5zYCBoYXMgYWxsIGl0J3MgcHJlZGljdG9ycyBlbmNvZGVkIGNvbmZpcm1pbmcgdGhhdCBpbmRlZWQgdGhlIHByZXByb2Nlc3Npbmcgc3RlcHMgZGVmaW5lZCBhcyBvdXIgcmVjaXBlIHdpbGwgd29yayBhcyBleHBlY3RlZC4gVGhpcyBtYWtlcyBpdCBoYXJkZXIgZm9yIHlvdSB0byByZWFkIGJ1dCBtdWNoIG1vcmUgaW50ZWxsaWdpYmxlIGZvciBUaWR5bW9kZWxzISBUYWtlIHNvbWUgdGltZSB0byBmaW5kIG91dCB3aGF0IG9ic2VydmF0aW9uIGhhcyBiZWVuIG1hcHBlZCB0byBhIGNvcnJlc3BvbmRpbmcgaW50ZWdlci4NCg0KSXQgaXMgYWxzbyB3b3J0aCBtZW50aW9uaW5nIHRoYXQgYGJha2VkX3B1bXBraW5zYCBpcyBhIGRhdGEgZnJhbWUgdGhhdCB3ZSBjYW4gcGVyZm9ybSBjb21wdXRhdGlvbnMgb24uDQoNCkZvciBpbnN0YW5jZSwgbGV0J3MgdHJ5IHRvIGZpbmQgYSBnb29kIGNvcnJlbGF0aW9uIGJldHdlZW4gdHdvIHBvaW50cyBvZiB5b3VyIGRhdGEgdG8gcG90ZW50aWFsbHkgYnVpbGQgYSBnb29kIHByZWRpY3RpdmUgbW9kZWwuIFdlJ2xsIHVzZSB0aGUgZnVuY3Rpb24gYGNvcigpYCB0byBkbyB0aGlzLiBUeXBlIGA/Y29yKClgIHRvIGZpbmQgb3V0IG1vcmUgYWJvdXQgdGhlIGZ1bmN0aW9uLg0KDQpgYGB7ciBjb3JyfQ0KIyBGaW5kIHRoZSBjb3JyZWxhdGlvbiBiZXR3ZWVuIHRoZSBjaXR5X25hbWUgYW5kIHRoZSBwcmljZQ0KY29yKGJha2VkX3B1bXBraW5zJGNpdHlfbmFtZSwgYmFrZWRfcHVtcGtpbnMkcHJpY2UpDQoNCiMgRmluZCB0aGUgY29ycmVsYXRpb24gYmV0d2VlbiB0aGUgcGFja2FnZSBhbmQgdGhlIHByaWNlDQpjb3IoYmFrZWRfcHVtcGtpbnMkcGFja2FnZSwgYmFrZWRfcHVtcGtpbnMkcHJpY2UpDQoNCmBgYA0KDQpBcyBpdCB0dXJucyBvdXQsIHRoZXJlJ3Mgb25seSB3ZWFrIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIENpdHkgYW5kIFByaWNlLiBIb3dldmVyIHRoZXJlJ3MgYSBiaXQgYmV0dGVyIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIFBhY2thZ2UgYW5kIGl0cyBQcmljZS4gVGhhdCBtYWtlcyBzZW5zZSwgcmlnaHQ/IE5vcm1hbGx5LCB0aGUgYmlnZ2VyIHRoZSBwcm9kdWNlIGJveCwgdGhlIGhpZ2hlciB0aGUgcHJpY2UuDQoNCldoaWxlIHdlIGFyZSBhdCBpdCwgbGV0J3MgYWxzbyB0cnkgYW5kIHZpc3VhbGl6ZSBhIGNvcnJlbGF0aW9uIG1hdHJpeCBvZiBhbGwgdGhlIGNvbHVtbnMgdXNpbmcgdGhlIGBjb3JycGxvdGAgcGFja2FnZS4NCg0KYGBge3IgY29ycnBsb3R9DQojIExvYWQgdGhlIGNvcnJwbG90IHBhY2thZ2UNCmxpYnJhcnkoY29ycnBsb3QpDQoNCiMgT2J0YWluIGNvcnJlbGF0aW9uIG1hdHJpeA0KY29ycl9tYXQgPC0gY29yKGJha2VkX3B1bXBraW5zICU+JSANCiAgICAgICAgICAgICAgICAgICMgRHJvcCBjb2x1bW5zIHRoYXQgYXJlIG5vdCByZWFsbHkgaW5mb3JtYXRpdmUNCiAgICAgICAgICAgICAgICAgIHNlbGVjdCgtYyhsb3dfcHJpY2UsIGhpZ2hfcHJpY2UpKSkNCg0KIyBNYWtlIGEgY29ycmVsYXRpb24gcGxvdCBiZXR3ZWVuIHRoZSB2YXJpYWJsZXMNCmNvcnJwbG90KGNvcnJfbWF0LCBtZXRob2QgPSAic2hhZGUiLCBzaGFkZS5jb2wgPSBOQSwgdGwuY29sID0gImJsYWNrIiwgdGwuc3J0ID0gNDUsIGFkZENvZWYuY29sID0gImJsYWNrIiwgY2wucG9zID0gIm4iLCBvcmRlciA9ICJvcmlnaW5hbCIpDQoNCmBgYA0KDQrwn6Sp8J+kqSBNdWNoIGJldHRlci4NCg0KQSBnb29kIHF1ZXN0aW9uIHRvIG5vdyBhc2sgb2YgdGhpcyBkYXRhIHdpbGwgYmU6ICdgV2hhdCBwcmljZSBjYW4gSSBleHBlY3Qgb2YgYSBnaXZlbiBwdW1wa2luIHBhY2thZ2U/YCcgTGV0J3MgZ2V0IHJpZ2h0IGludG8gaXQhDQoNCj4gTm90ZTogV2hlbiB5b3UgKipgYmFrZSgpYCoqIHRoZSBwcmVwcGVkIHJlY2lwZSAqKmBwdW1wa2luc19wcmVwYCoqIHdpdGggKipgbmV3X2RhdGEgPSBOVUxMYCoqLCB5b3UgZXh0cmFjdCB0aGUgcHJvY2Vzc2VkIChpLmUuIGVuY29kZWQpIHRyYWluaW5nIGRhdGEuIElmIHlvdSBoYWQgYW5vdGhlciBkYXRhIHNldCBmb3IgZXhhbXBsZSBhIHRlc3Qgc2V0IGFuZCB3b3VsZCB3YW50IHRvIHNlZSBob3cgYSByZWNpcGUgd291bGQgcHJlLXByb2Nlc3MgaXQsIHlvdSB3b3VsZCBzaW1wbHkgYmFrZSAqKmBwdW1wa2luc19wcmVwYCoqIHdpdGggKipgbmV3X2RhdGEgPSB0ZXN0X3NldGAqKg0KDQojIyA0LiBCdWlsZCBhIGxpbmVhciByZWdyZXNzaW9uIG1vZGVsDQoNCiFbSW5mb2dyYXBoaWMgYnkgRGFzYW5pIE1hZGlwYWxsaV0oLi4vLi4vaW1hZ2VzL2xpbmVhci1wb2x5bm9taWFsLnBuZyl7d2lkdGg9IjgwMCJ9DQoNCk5vdyB0aGF0IHdlIGhhdmUgYnVpbGQgYSByZWNpcGUsIGFuZCBhY3R1YWxseSBjb25maXJtZWQgdGhhdCB0aGUgZGF0YSB3aWxsIGJlIHByZS1wcm9jZXNzZWQgYXBwcm9wcmlhdGVseSwgbGV0J3Mgbm93IGJ1aWxkIGEgcmVncmVzc2lvbiBtb2RlbCB0byBhbnN3ZXIgdGhlIHF1ZXN0aW9uOiBgV2hhdCBwcmljZSBjYW4gSSBleHBlY3Qgb2YgYSBnaXZlbiBwdW1wa2luIHBhY2thZ2U/YA0KDQojIyMjIFRyYWluIGEgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgdXNpbmcgdGhlIHRyYWluaW5nIHNldA0KDQpBcyB5b3UgbWF5IGhhdmUgYWxyZWFkeSBmaWd1cmVkIG91dCwgdGhlIGNvbHVtbiAqcHJpY2UqIGlzIHRoZSBgb3V0Y29tZWAgdmFyaWFibGUgd2hpbGUgdGhlICpwYWNrYWdlKiBjb2x1bW4gaXMgdGhlIGBwcmVkaWN0b3JgIHZhcmlhYmxlLg0KDQpUbyBkbyB0aGlzLCB3ZSdsbCBmaXJzdCBzcGxpdCB0aGUgZGF0YSBzdWNoIHRoYXQgODAlIGdvZXMgaW50byB0cmFpbmluZyBhbmQgMjAlIGludG8gdGVzdCBzZXQsIHRoZW4gZGVmaW5lIGEgcmVjaXBlIHRoYXQgd2lsbCBlbmNvZGUgdGhlIHByZWRpY3RvciBjb2x1bW4gaW50byBhIHNldCBvZiBpbnRlZ2VycywgdGhlbiBidWlsZCBhIG1vZGVsIHNwZWNpZmljYXRpb24uIFdlIHdvbid0IHByZXAgYW5kIGJha2Ugb3VyIHJlY2lwZSBzaW5jZSB3ZSBhbHJlYWR5IGtub3cgaXQgd2lsbCBwcmVwcm9jZXNzIHRoZSBkYXRhIGFzIGV4cGVjdGVkLg0KDQpgYGB7ciBsbV9yZWNfc3BlY30NCnNldC5zZWVkKDIwNTYpDQojIFNwbGl0IHRoZSBkYXRhIGludG8gdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cw0KcHVtcGtpbnNfc3BsaXQgPC0gbmV3X3B1bXBraW5zICU+JSANCiAgaW5pdGlhbF9zcGxpdChwcm9wID0gMC44KQ0KDQoNCiMgRXh0cmFjdCB0cmFpbmluZyBhbmQgdGVzdCBkYXRhDQpwdW1wa2luc190cmFpbiA8LSB0cmFpbmluZyhwdW1wa2luc19zcGxpdCkNCnB1bXBraW5zX3Rlc3QgPC0gdGVzdGluZyhwdW1wa2luc19zcGxpdCkNCg0KDQoNCiMgQ3JlYXRlIGEgcmVjaXBlIGZvciBwcmVwcm9jZXNzaW5nIHRoZSBkYXRhDQpsbV9wdW1wa2luc19yZWNpcGUgPC0gcmVjaXBlKHByaWNlIH4gcGFja2FnZSwgZGF0YSA9IHB1bXBraW5zX3RyYWluKSAlPiUgDQogIHN0ZXBfaW50ZWdlcihhbGxfcHJlZGljdG9ycygpLCB6ZXJvX2Jhc2VkID0gVFJVRSkNCg0KDQoNCiMgQ3JlYXRlIGEgbGluZWFyIG1vZGVsIHNwZWNpZmljYXRpb24NCmxtX3NwZWMgPC0gbGluZWFyX3JlZygpICU+JSANCiAgc2V0X2VuZ2luZSgibG0iKSAlPiUgDQogIHNldF9tb2RlKCJyZWdyZXNzaW9uIikNCg0KDQpgYGANCg0KR29vZCBqb2IhIE5vdyB0aGF0IHdlIGhhdmUgYSByZWNpcGUgYW5kIGEgbW9kZWwgc3BlY2lmaWNhdGlvbiwgd2UgbmVlZCB0byBmaW5kIGEgd2F5IG9mIGJ1bmRsaW5nIHRoZW0gdG9nZXRoZXIgaW50byBhbiBvYmplY3QgdGhhdCB3aWxsIGZpcnN0IHByZXByb2Nlc3MgdGhlIGRhdGEgKHByZXArYmFrZSBiZWhpbmQgdGhlIHNjZW5lcyksIGZpdCB0aGUgbW9kZWwgb24gdGhlIHByZXByb2Nlc3NlZCBkYXRhIGFuZCBhbHNvIGFsbG93IGZvciBwb3RlbnRpYWwgcG9zdC1wcm9jZXNzaW5nIGFjdGl2aXRpZXMuIEhvdydzIHRoYXQgZm9yIHlvdXIgcGVhY2Ugb2YgbWluZCHwn6SpDQoNCkluIFRpZHltb2RlbHMsIHRoaXMgY29udmVuaWVudCBvYmplY3QgaXMgY2FsbGVkIGEgW2B3b3JrZmxvd2BdKGh0dHBzOi8vd29ya2Zsb3dzLnRpZHltb2RlbHMub3JnLykgYW5kIGNvbnZlbmllbnRseSBob2xkcyB5b3VyIG1vZGVsaW5nIGNvbXBvbmVudHMhIFRoaXMgaXMgd2hhdCB3ZSdkIGNhbGwgKnBpcGVsaW5lcyogaW4gKlB5dGhvbiouDQoNClNvIGxldCdzIGJ1bmRsZSBldmVyeXRoaW5nIHVwIGludG8gYSB3b3JrZmxvdyHwn5OmDQoNCmBgYHtyIGxtX3dvcmtmbG93fQ0KIyBIb2xkIG1vZGVsbGluZyBjb21wb25lbnRzIGluIGEgd29ya2Zsb3cNCmxtX3dmIDwtIHdvcmtmbG93KCkgJT4lIA0KICBhZGRfcmVjaXBlKGxtX3B1bXBraW5zX3JlY2lwZSkgJT4lIA0KICBhZGRfbW9kZWwobG1fc3BlYykNCg0KIyBQcmludCBvdXQgdGhlIHdvcmtmbG93DQpsbV93Zg0KDQpgYGANCg0K8J+RjCBJbnRvIHRoZSBiYXJnYWluLCBhIHdvcmtmbG93IGNhbiBiZSBmaXQvdHJhaW5lZCBpbiBtdWNoIHRoZSBzYW1lIHdheSBhIG1vZGVsIGNhbi4NCg0KYGBge3IgbG1fd2ZfZml0fQ0KIyBUcmFpbiB0aGUgbW9kZWwNCmxtX3dmX2ZpdCA8LSBsbV93ZiAlPiUgDQogIGZpdChkYXRhID0gcHVtcGtpbnNfdHJhaW4pDQoNCiMgUHJpbnQgdGhlIG1vZGVsIGNvZWZmaWNpZW50cyBsZWFybmVkIA0KbG1fd2ZfZml0DQoNCmBgYA0KDQpGcm9tIHRoZSBtb2RlbCBvdXRwdXQsIHdlIGNhbiBzZWUgdGhlIGNvZWZmaWNpZW50cyBsZWFybmVkIGR1cmluZyB0cmFpbmluZy4gVGhleSByZXByZXNlbnQgdGhlIGNvZWZmaWNpZW50cyBvZiB0aGUgbGluZSBvZiBiZXN0IGZpdCB0aGF0IGdpdmVzIHVzIHRoZSBsb3dlc3Qgb3ZlcmFsbCBlcnJvciBiZXR3ZWVuIHRoZSBhY3R1YWwgYW5kIHByZWRpY3RlZCB2YXJpYWJsZS4NCg0KIyMjIyBFdmFsdWF0ZSBtb2RlbCBwZXJmb3JtYW5jZSB1c2luZyB0aGUgdGVzdCBzZXQNCg0KSXQncyB0aW1lIHRvIHNlZSBob3cgdGhlIG1vZGVsIHBlcmZvcm1lZCDwn5OPISBIb3cgZG8gd2UgZG8gdGhpcz8NCg0KTm93IHRoYXQgd2UndmUgdHJhaW5lZCB0aGUgbW9kZWwsIHdlIGNhbiB1c2UgaXQgdG8gbWFrZSBwcmVkaWN0aW9ucyBmb3IgdGhlIHRlc3Rfc2V0IHVzaW5nIGBwYXJzbmlwOjpwcmVkaWN0KClgLiBUaGVuIHdlIGNhbiBjb21wYXJlIHRoZXNlIHByZWRpY3Rpb25zIHRvIHRoZSBhY3R1YWwgbGFiZWwgdmFsdWVzIHRvIGV2YWx1YXRlIGhvdyB3ZWxsIChvciBub3QhKSB0aGUgbW9kZWwgaXMgd29ya2luZy4NCg0KTGV0J3Mgc3RhcnQgd2l0aCBtYWtpbmcgcHJlZGljdGlvbnMgZm9yIHRoZSB0ZXN0IHNldCB0aGVuIGJpbmQgdGhlIGNvbHVtbnMgdG8gdGhlIHRlc3Qgc2V0Lg0KDQpgYGB7ciBsbV9wcmVkfQ0KIyBNYWtlIHByZWRpY3Rpb25zIGZvciB0aGUgdGVzdCBzZXQNCnByZWRpY3Rpb25zIDwtIGxtX3dmX2ZpdCAlPiUgDQogIHByZWRpY3QobmV3X2RhdGEgPSBwdW1wa2luc190ZXN0KQ0KDQoNCiMgQmluZCBwcmVkaWN0aW9ucyB0byB0aGUgdGVzdCBzZXQNCmxtX3Jlc3VsdHMgPC0gcHVtcGtpbnNfdGVzdCAlPiUgDQogIHNlbGVjdChjKHBhY2thZ2UsIHByaWNlKSkgJT4lIA0KICBiaW5kX2NvbHMocHJlZGljdGlvbnMpDQoNCg0KIyBQcmludCB0aGUgZmlyc3QgdGVuIHJvd3Mgb2YgdGhlIHRpYmJsZQ0KbG1fcmVzdWx0cyAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDEwKQ0KYGBgDQoNClllcywgeW91IGhhdmUganVzdCB0cmFpbmVkIGEgbW9kZWwgYW5kIHVzZWQgaXQgdG8gbWFrZSBwcmVkaWN0aW9ucyHwn5SuIElzIGl0IGFueSBnb29kLCBsZXQncyBldmFsdWF0ZSB0aGUgbW9kZWwncyBwZXJmb3JtYW5jZSENCg0KSW4gVGlkeW1vZGVscywgd2UgZG8gdGhpcyB1c2luZyBgeWFyZHN0aWNrOjptZXRyaWNzKClgISBGb3IgbGluZWFyIHJlZ3Jlc3Npb24sIGxldCdzIGZvY3VzIG9uIHRoZSBmb2xsb3dpbmcgbWV0cmljczoNCg0KLSAgIGBSb290IE1lYW4gU3F1YXJlIEVycm9yIChSTVNFKWA6IFRoZSBzcXVhcmUgcm9vdCBvZiB0aGUgW01TRV0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTWVhbl9zcXVhcmVkX2Vycm9yKS4gVGhpcyB5aWVsZHMgYW4gYWJzb2x1dGUgbWV0cmljIGluIHRoZSBzYW1lIHVuaXQgYXMgdGhlIGxhYmVsIChpbiB0aGlzIGNhc2UsIHRoZSBwcmljZSBvZiBhIHB1bXBraW4pLiBUaGUgc21hbGxlciB0aGUgdmFsdWUsIHRoZSBiZXR0ZXIgdGhlIG1vZGVsIChpbiBhIHNpbXBsaXN0aWMgc2Vuc2UsIGl0IHJlcHJlc2VudHMgdGhlIGF2ZXJhZ2UgcHJpY2UgYnkgd2hpY2ggdGhlIHByZWRpY3Rpb25zIGFyZSB3cm9uZyEpDQoNCi0gICBgQ29lZmZpY2llbnQgb2YgRGV0ZXJtaW5hdGlvbiAodXN1YWxseSBrbm93biBhcyBSLXNxdWFyZWQgb3IgUjIpYDogQSByZWxhdGl2ZSBtZXRyaWMgaW4gd2hpY2ggdGhlIGhpZ2hlciB0aGUgdmFsdWUsIHRoZSBiZXR0ZXIgdGhlIGZpdCBvZiB0aGUgbW9kZWwuIEluIGVzc2VuY2UsIHRoaXMgbWV0cmljIHJlcHJlc2VudHMgaG93IG11Y2ggb2YgdGhlIHZhcmlhbmNlIGJldHdlZW4gcHJlZGljdGVkIGFuZCBhY3R1YWwgbGFiZWwgdmFsdWVzIHRoZSBtb2RlbCBpcyBhYmxlIHRvIGV4cGxhaW4uDQoNCmBgYHtyIGxtX3lhcmRzdGlja30NCiMgRXZhbHVhdGUgcGVyZm9ybWFuY2Ugb2YgbGluZWFyIHJlZ3Jlc3Npb24NCm1ldHJpY3MoZGF0YSA9IGxtX3Jlc3VsdHMsDQogICAgICAgIHRydXRoID0gcHJpY2UsDQogICAgICAgIGVzdGltYXRlID0gLnByZWQpDQoNCg0KYGBgDQoNClRoZXJlIGdvZXMgdGhlIG1vZGVsIHBlcmZvcm1hbmNlLiBMZXQncyBzZWUgaWYgd2UgY2FuIGdldCBhIGJldHRlciBpbmRpY2F0aW9uIGJ5IHZpc3VhbGl6aW5nIGEgc2NhdHRlciBwbG90IG9mIHRoZSBwYWNrYWdlIGFuZCBwcmljZSB0aGVuIHVzZSB0aGUgcHJlZGljdGlvbnMgbWFkZSB0byBvdmVybGF5IGEgbGluZSBvZiBiZXN0IGZpdC4NCg0KVGhpcyBtZWFucyB3ZSdsbCBoYXZlIHRvIHByZXAgYW5kIGJha2UgdGhlIHRlc3Qgc2V0IGluIG9yZGVyIHRvIGVuY29kZSB0aGUgcGFja2FnZSBjb2x1bW4gdGhlbiBiaW5kIHRoaXMgdG8gdGhlIHByZWRpY3Rpb25zIG1hZGUgYnkgb3VyIG1vZGVsLg0KDQpgYGB7ciBsbV9wbG90fQ0KIyBFbmNvZGUgcGFja2FnZSBjb2x1bW4NCnBhY2thZ2VfZW5jb2RlIDwtIGxtX3B1bXBraW5zX3JlY2lwZSAlPiUgDQogIHByZXAoKSAlPiUgDQogIGJha2UobmV3X2RhdGEgPSBwdW1wa2luc190ZXN0KSAlPiUgDQogIHNlbGVjdChwYWNrYWdlKQ0KDQoNCiMgQmluZCBlbmNvZGVkIHBhY2thZ2UgY29sdW1uIHRvIHRoZSByZXN1bHRzDQpsbV9yZXN1bHRzIDwtIGxtX3Jlc3VsdHMgJT4lIA0KICBiaW5kX2NvbHMocGFja2FnZV9lbmNvZGUgJT4lIA0KICAgICAgICAgICAgICByZW5hbWUocGFja2FnZV9pbnRlZ2VyID0gcGFja2FnZSkpICU+JSANCiAgcmVsb2NhdGUocGFja2FnZV9pbnRlZ2VyLCAuYWZ0ZXIgPSBwYWNrYWdlKQ0KDQoNCiMgUHJpbnQgbmV3IHJlc3VsdHMgZGF0YSBmcmFtZQ0KbG1fcmVzdWx0cyAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDUpDQoNCg0KIyBNYWtlIGEgc2NhdHRlciBwbG90DQpsbV9yZXN1bHRzICU+JSANCiAgZ2dwbG90KG1hcHBpbmcgPSBhZXMoeCA9IHBhY2thZ2VfaW50ZWdlciwgeSA9IHByaWNlKSkgKw0KICBnZW9tX3BvaW50KHNpemUgPSAxLjYpICsNCiAgIyBPdmVybGF5IGEgbGluZSBvZiBiZXN0IGZpdA0KICBnZW9tX2xpbmUoYWVzKHkgPSAucHJlZCksIGNvbG9yID0gIm9yYW5nZSIsIHNpemUgPSAxLjIpICsNCiAgeGxhYigicGFja2FnZSIpDQogIA0KDQoNCmBgYA0KDQpHcmVhdCEgQXMgeW91IGNhbiBzZWUsIHRoZSBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbCBkb2VzIG5vdCByZWFsbHkgd2VsbCBnZW5lcmFsaXplIHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiBhIHBhY2thZ2UgYW5kIGl0cyBjb3JyZXNwb25kaW5nIHByaWNlLg0KDQrwn46DIENvbmdyYXR1bGF0aW9ucywgeW91IGp1c3QgY3JlYXRlZCBhIG1vZGVsIHRoYXQgY2FuIGhlbHAgcHJlZGljdCB0aGUgcHJpY2Ugb2YgYSBmZXcgdmFyaWV0aWVzIG9mIHB1bXBraW5zLiBZb3VyIGhvbGlkYXkgcHVtcGtpbiBwYXRjaCB3aWxsIGJlIGJlYXV0aWZ1bC4gQnV0IHlvdSBjYW4gcHJvYmFibHkgY3JlYXRlIGEgYmV0dGVyIG1vZGVsIQ0KDQojIyA1LiBCdWlsZCBhIHBvbHlub21pYWwgcmVncmVzc2lvbiBtb2RlbA0KDQohW0luZm9ncmFwaGljIGJ5IERhc2FuaSBNYWRpcGFsbGldKC4uLy4uL2ltYWdlcy9saW5lYXItcG9seW5vbWlhbC5wbmcpe3dpZHRoPSI4MDAifQ0KDQpTb21ldGltZXMgb3VyIGRhdGEgbWF5IG5vdCBoYXZlIGEgbGluZWFyIHJlbGF0aW9uc2hpcCwgYnV0IHdlIHN0aWxsIHdhbnQgdG8gcHJlZGljdCBhbiBvdXRjb21lLiBQb2x5bm9taWFsIHJlZ3Jlc3Npb24gY2FuIGhlbHAgdXMgbWFrZSBwcmVkaWN0aW9ucyBmb3IgbW9yZSBjb21wbGV4IG5vbi1saW5lYXIgcmVsYXRpb25zaGlwcy4NCg0KVGFrZSBmb3IgaW5zdGFuY2UgdGhlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIHRoZSBwYWNrYWdlIGFuZCBwcmljZSBmb3Igb3VyIHB1bXBraW5zIGRhdGEgc2V0LiBXaGlsZSBzb21ldGltZXMgdGhlcmUncyBhIGxpbmVhciByZWxhdGlvbnNoaXAgYmV0d2VlbiB2YXJpYWJsZXMgLSB0aGUgYmlnZ2VyIHRoZSBwdW1wa2luIGluIHZvbHVtZSwgdGhlIGhpZ2hlciB0aGUgcHJpY2UgLSBzb21ldGltZXMgdGhlc2UgcmVsYXRpb25zaGlwcyBjYW4ndCBiZSBwbG90dGVkIGFzIGEgcGxhbmUgb3Igc3RyYWlnaHQgbGluZS4NCg0KPiDinIUgSGVyZSBhcmUgW3NvbWUgbW9yZSBleGFtcGxlc10oaHR0cHM6Ly9vbmxpbmUuc3RhdC5wc3UuZWR1L3N0YXQ1MDEvbGVzc29uLzkvOS44KSBvZiBkYXRhIHRoYXQgY291bGQgdXNlIHBvbHlub21pYWwgcmVncmVzc2lvbg0KPg0KPiBUYWtlIGFub3RoZXIgbG9vayBhdCB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gVmFyaWV0eSB0byBQcmljZSBpbiB0aGUgcHJldmlvdXMgcGxvdC4gRG9lcyB0aGlzIHNjYXR0ZXJwbG90IHNlZW0gbGlrZSBpdCBzaG91bGQgbmVjZXNzYXJpbHkgYmUgYW5hbHl6ZWQgYnkgYSBzdHJhaWdodCBsaW5lPyBQZXJoYXBzIG5vdC4gSW4gdGhpcyBjYXNlLCB5b3UgY2FuIHRyeSBwb2x5bm9taWFsIHJlZ3Jlc3Npb24uDQo+DQo+IOKchSBQb2x5bm9taWFscyBhcmUgbWF0aGVtYXRpY2FsIGV4cHJlc3Npb25zIHRoYXQgbWlnaHQgY29uc2lzdCBvZiBvbmUgb3IgbW9yZSB2YXJpYWJsZXMgYW5kIGNvZWZmaWNpZW50cw0KDQojIyMjIFRyYWluIGEgcG9seW5vbWlhbCByZWdyZXNzaW9uIG1vZGVsIHVzaW5nIHRoZSB0cmFpbmluZyBzZXQNCg0KUG9seW5vbWlhbCByZWdyZXNzaW9uIGNyZWF0ZXMgYSAqY3VydmVkIGxpbmUqIHRvIGJldHRlciBmaXQgbm9ubGluZWFyIGRhdGEuDQoNCkxldCdzIHNlZSB3aGV0aGVyIGEgcG9seW5vbWlhbCBtb2RlbCB3aWxsIHBlcmZvcm0gYmV0dGVyIGluIG1ha2luZyBwcmVkaWN0aW9ucy4gV2UnbGwgZm9sbG93IGEgc29tZXdoYXQgc2ltaWxhciBwcm9jZWR1cmUgYXMgd2UgZGlkIGJlZm9yZToNCg0KLSAgIENyZWF0ZSBhIHJlY2lwZSB0aGF0IHNwZWNpZmllcyB0aGUgcHJlcHJvY2Vzc2luZyBzdGVwcyB0aGF0IHNob3VsZCBiZSBjYXJyaWVkIG91dCBvbiBvdXIgZGF0YSB0byBnZXQgaXQgcmVhZHkgZm9yIG1vZGVsbGluZyBpLmU6IGVuY29kaW5nIHByZWRpY3RvcnMgYW5kIGNvbXB1dGluZyBwb2x5bm9taWFscyBvZiBkZWdyZWUgKm4qDQoNCi0gICBCdWlsZCBhIG1vZGVsIHNwZWNpZmljYXRpb24NCg0KLSAgIEJ1bmRsZSB0aGUgcmVjaXBlIGFuZCBtb2RlbCBzcGVjaWZpY2F0aW9uIGludG8gYSB3b3JrZmxvdw0KDQotICAgQ3JlYXRlIGEgbW9kZWwgYnkgZml0dGluZyB0aGUgd29ya2Zsb3cNCg0KLSAgIEV2YWx1YXRlIGhvdyB3ZWxsIHRoZSBtb2RlbCBwZXJmb3JtcyBvbiB0aGUgdGVzdCBkYXRhDQoNCkxldCdzIGdldCByaWdodCBpbnRvIGl0IQ0KDQpgYGB7ciBwb2x5bm9taWFsX3JlZ30NCiMgU3BlY2lmeSBhIHJlY2lwZQ0KcG9seV9wdW1wa2luc19yZWNpcGUgPC0NCiAgcmVjaXBlKHByaWNlIH4gcGFja2FnZSwgZGF0YSA9IHB1bXBraW5zX3RyYWluKSAlPiUNCiAgc3RlcF9pbnRlZ2VyKGFsbF9wcmVkaWN0b3JzKCksIHplcm9fYmFzZWQgPSBUUlVFKSAlPiUgDQogIHN0ZXBfcG9seShhbGxfcHJlZGljdG9ycygpLCBkZWdyZWUgPSA0KQ0KDQoNCiMgQ3JlYXRlIGEgbW9kZWwgc3BlY2lmaWNhdGlvbg0KcG9seV9zcGVjIDwtIGxpbmVhcl9yZWcoKSAlPiUgDQogIHNldF9lbmdpbmUoImxtIikgJT4lIA0KICBzZXRfbW9kZSgicmVncmVzc2lvbiIpDQoNCg0KIyBCdW5kbGUgcmVjaXBlIGFuZCBtb2RlbCBzcGVjIGludG8gYSB3b3JrZmxvdw0KcG9seV93ZiA8LSB3b3JrZmxvdygpICU+JSANCiAgYWRkX3JlY2lwZShwb2x5X3B1bXBraW5zX3JlY2lwZSkgJT4lIA0KICBhZGRfbW9kZWwocG9seV9zcGVjKQ0KDQoNCiMgQ3JlYXRlIGEgbW9kZWwNCnBvbHlfd2ZfZml0IDwtIHBvbHlfd2YgJT4lIA0KICBmaXQoZGF0YSA9IHB1bXBraW5zX3RyYWluKQ0KDQoNCiMgUHJpbnQgbGVhcm5lZCBtb2RlbCBjb2VmZmljaWVudHMNCnBvbHlfd2ZfZml0DQoNCiAgDQoNCmBgYA0KDQojIyMjIEV2YWx1YXRlIG1vZGVsIHBlcmZvcm1hbmNlDQoNCvCfkY/wn5GPWW91J3ZlIGJ1aWx0IGEgcG9seW5vbWlhbCBtb2RlbCBsZXQncyBtYWtlIHByZWRpY3Rpb25zIG9uIHRoZSB0ZXN0IHNldCENCg0KYGBge3IgcG9seV9wcmVkaWN0fQ0KIyBNYWtlIHByaWNlIHByZWRpY3Rpb25zIG9uIHRlc3QgZGF0YQ0KcG9seV9yZXN1bHRzIDwtIHBvbHlfd2ZfZml0ICU+JSBwcmVkaWN0KG5ld19kYXRhID0gcHVtcGtpbnNfdGVzdCkgJT4lIA0KICBiaW5kX2NvbHMocHVtcGtpbnNfdGVzdCAlPiUgc2VsZWN0KGMocGFja2FnZSwgcHJpY2UpKSkgJT4lIA0KICByZWxvY2F0ZSgucHJlZCwgLmFmdGVyID0gbGFzdF9jb2woKSkNCg0KDQojIFByaW50IHRoZSByZXN1bHRzDQpwb2x5X3Jlc3VsdHMgJT4lIA0KICBzbGljZV9oZWFkKG4gPSAxMCkNCmBgYA0KDQpXb28taG9vICwgbGV0J3MgZXZhbHVhdGUgaG93IHRoZSBtb2RlbCBwZXJmb3JtZWQgb24gdGhlIHRlc3Rfc2V0IHVzaW5nIGB5YXJkc3RpY2s6Om1ldHJpY3MoKWAuDQoNCmBgYHtyIHBvbHlfZXZhbH0NCm1ldHJpY3MoZGF0YSA9IHBvbHlfcmVzdWx0cywgdHJ1dGggPSBwcmljZSwgZXN0aW1hdGUgPSAucHJlZCkNCmBgYA0KDQrwn6Sp8J+kqSBNdWNoIGJldHRlciBwZXJmb3JtYW5jZS4NCg0KVGhlIGBybXNlYCBkZWNyZWFzZWQgZnJvbSBhYm91dCA3LiB0byBhYm91dCAzLiBhbiBpbmRpY2F0aW9uIHRoYXQgb2YgYSByZWR1Y2VkIGVycm9yIGJldHdlZW4gdGhlIGFjdHVhbCBwcmljZSBhbmQgdGhlIHByZWRpY3RlZCBwcmljZS4gWW91IGNhbiAqbG9vc2VseSogaW50ZXJwcmV0IHRoaXMgYXMgbWVhbmluZyB0aGF0IG9uIGF2ZXJhZ2UsIGluY29ycmVjdCBwcmVkaWN0aW9ucyBhcmUgd3JvbmcgYnkgYXJvdW5kIFwkMy4gVGhlIGByc3FgIGluY3JlYXNlZCBmcm9tIGFib3V0IDAuNCB0byAwLjguDQoNCkFsbCB0aGVzZSBtZXRyaWNzIGluZGljYXRlIHRoYXQgdGhlIHBvbHlub21pYWwgbW9kZWwgcGVyZm9ybXMgd2F5IGJldHRlciB0aGFuIHRoZSBsaW5lYXIgbW9kZWwuIEdvb2Qgam9iIQ0KDQpMZXQncyBzZWUgaWYgd2UgY2FuIHZpc3VhbGl6ZSB0aGlzIQ0KDQpgYGB7ciBwb2x5X3Zpen0NCiMgQmluZCBlbmNvZGVkIHBhY2thZ2UgY29sdW1uIHRvIHRoZSByZXN1bHRzDQpwb2x5X3Jlc3VsdHMgPC0gcG9seV9yZXN1bHRzICU+JSANCiAgYmluZF9jb2xzKHBhY2thZ2VfZW5jb2RlICU+JSANCiAgICAgICAgICAgICAgcmVuYW1lKHBhY2thZ2VfaW50ZWdlciA9IHBhY2thZ2UpKSAlPiUgDQogIHJlbG9jYXRlKHBhY2thZ2VfaW50ZWdlciwgLmFmdGVyID0gcGFja2FnZSkNCg0KDQojIFByaW50IG5ldyByZXN1bHRzIGRhdGEgZnJhbWUNCnBvbHlfcmVzdWx0cyAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDUpDQoNCg0KIyBNYWtlIGEgc2NhdHRlciBwbG90DQpwb2x5X3Jlc3VsdHMgJT4lIA0KICBnZ3Bsb3QobWFwcGluZyA9IGFlcyh4ID0gcGFja2FnZV9pbnRlZ2VyLCB5ID0gcHJpY2UpKSArDQogIGdlb21fcG9pbnQoc2l6ZSA9IDEuNikgKw0KICAjIE92ZXJsYXkgYSBsaW5lIG9mIGJlc3QgZml0DQogIGdlb21fbGluZShhZXMoeSA9IC5wcmVkKSwgY29sb3IgPSAibWlkbmlnaHRibHVlIiwgc2l6ZSA9IDEuMikgKw0KICB4bGFiKCJwYWNrYWdlIikNCg0KDQoNCmBgYA0KDQpZb3UgY2FuIHNlZSBhIGN1cnZlZCBsaW5lIHRoYXQgZml0cyB5b3VyIGRhdGEgYmV0dGVyISDwn6SpDQoNCllvdSBjYW4gbWFrZSB0aGlzIG1vcmUgc21vb3RoZXIgYnkgcGFzc2luZyBhIHBvbHlub21pYWwgZm9ybXVsYSB0byBgZ2VvbV9zbW9vdGhgIGxpa2UgdGhpczoNCg0KYGBge3Igc21vb3RoIGN1cnZlfQ0KIyBNYWtlIGEgc2NhdHRlciBwbG90DQpwb2x5X3Jlc3VsdHMgJT4lIA0KICBnZ3Bsb3QobWFwcGluZyA9IGFlcyh4ID0gcGFja2FnZV9pbnRlZ2VyLCB5ID0gcHJpY2UpKSArDQogIGdlb21fcG9pbnQoc2l6ZSA9IDEuNikgKw0KICAjIE92ZXJsYXkgYSBsaW5lIG9mIGJlc3QgZml0DQogIGdlb21fc21vb3RoKG1ldGhvZCA9IGxtLCBmb3JtdWxhID0geSB+IHBvbHkoeCwgZGVncmVlID0gNCksIGNvbG9yID0gIm1pZG5pZ2h0Ymx1ZSIsIHNpemUgPSAxLjIsIHNlID0gRkFMU0UpICsNCiAgeGxhYigicGFja2FnZSIpDQoNCg0KDQoNCmBgYA0KDQpNdWNoIGxpa2UgYSBzbW9vdGggY3VydmUh8J+kqQ0KDQpIZXJlJ3MgaG93IHlvdSB3b3VsZCBtYWtlIGEgbmV3IHByZWRpY3Rpb246DQoNCmBgYHtyIHByZWRpY3R9DQojIE1ha2UgYSBoeXBvdGhldGljYWwgZGF0YSBmcmFtZQ0KaHlwb190aWJibGUgPC0gdGliYmxlKHBhY2thZ2UgPSAiYnVzaGVsIGJhc2tldHMiKQ0KDQojIE1ha2UgcHJlZGljdGlvbnMgdXNpbmcgbGluZWFyIG1vZGVsDQpsbV9wcmVkIDwtIGxtX3dmX2ZpdCAlPiUgcHJlZGljdChuZXdfZGF0YSA9IGh5cG9fdGliYmxlKQ0KDQojIE1ha2UgcHJlZGljdGlvbnMgdXNpbmcgcG9seW5vbWlhbCBtb2RlbA0KcG9seV9wcmVkIDwtIHBvbHlfd2ZfZml0ICU+JSBwcmVkaWN0KG5ld19kYXRhID0gaHlwb190aWJibGUpDQoNCiMgUmV0dXJuIHByZWRpY3Rpb25zIGluIGEgbGlzdA0KbGlzdCgibGluZWFyIG1vZGVsIHByZWRpY3Rpb24iID0gbG1fcHJlZCwgDQogICAgICJwb2x5bm9taWFsIG1vZGVsIHByZWRpY3Rpb24iID0gcG9seV9wcmVkKQ0KDQoNCmBgYA0KDQpUaGUgYHBvbHlub21pYWwgbW9kZWxgIHByZWRpY3Rpb24gZG9lcyBtYWtlIHNlbnNlLCBnaXZlbiB0aGUgc2NhdHRlciBwbG90cyBvZiBgcHJpY2VgIGFuZCBgcGFja2FnZWAhIEFuZCwgaWYgdGhpcyBpcyBhIGJldHRlciBtb2RlbCB0aGFuIHRoZSBwcmV2aW91cyBvbmUsIGxvb2tpbmcgYXQgdGhlIHNhbWUgZGF0YSwgeW91IG5lZWQgdG8gYnVkZ2V0IGZvciB0aGVzZSBtb3JlIGV4cGVuc2l2ZSBwdW1wa2lucyENCg0K8J+PhiBXZWxsIGRvbmUhIFlvdSBjcmVhdGVkIHR3byByZWdyZXNzaW9uIG1vZGVscyBpbiBvbmUgbGVzc29uLiBJbiB0aGUgZmluYWwgc2VjdGlvbiBvbiByZWdyZXNzaW9uLCB5b3Ugd2lsbCBsZWFybiBhYm91dCBsb2dpc3RpYyByZWdyZXNzaW9uIHRvIGRldGVybWluZSBjYXRlZ29yaWVzLg0KDQojIyAqKvCfmoBDaGFsbGVuZ2UqKg0KDQpUZXN0IHNldmVyYWwgZGlmZmVyZW50IHZhcmlhYmxlcyBpbiB0aGlzIG5vdGVib29rIHRvIHNlZSBob3cgY29ycmVsYXRpb24gY29ycmVzcG9uZHMgdG8gbW9kZWwgYWNjdXJhY3kuDQoNCiMjIFsqKlBvc3QtbGVjdHVyZSBxdWl6KipdKGh0dHBzOi8vZ3JheS1zYW5kLTA3YTEwZjQwMy4xLmF6dXJlc3RhdGljYXBwcy5uZXQvcXVpei8xNC8pDQoNCiMjICoqUmV2aWV3ICYgU2VsZiBTdHVkeSoqDQoNCkluIHRoaXMgbGVzc29uIHdlIGxlYXJuZWQgYWJvdXQgTGluZWFyIFJlZ3Jlc3Npb24uIFRoZXJlIGFyZSBvdGhlciBpbXBvcnRhbnQgdHlwZXMgb2YgUmVncmVzc2lvbi4gUmVhZCBhYm91dCBTdGVwd2lzZSwgUmlkZ2UsIExhc3NvIGFuZCBFbGFzdGljbmV0IHRlY2huaXF1ZXMuIEEgZ29vZCBjb3Vyc2UgdG8gc3R1ZHkgdG8gbGVhcm4gbW9yZSBpcyB0aGUgW1N0YW5mb3JkIFN0YXRpc3RpY2FsIExlYXJuaW5nIGNvdXJzZV0oaHR0cHM6Ly9vbmxpbmUuc3RhbmZvcmQuZWR1L2NvdXJzZXMvc29ocy15c3RhdHNsZWFybmluZy1zdGF0aXN0aWNhbC1sZWFybmluZykNCg0KSWYgeW91IHdhbnQgdG8gbGVhcm4gbW9yZSBhYm91dCBob3cgdG8gdXNlIHRoZSBhbWF6aW5nIFRpZHltb2RlbHMgZnJhbWV3b3JrLCBwbGVhc2UgY2hlY2sgb3V0IHRoZSBmb2xsb3dpbmcgcmVzb3VyY2VzOg0KDQotICAgVGlkeW1vZGVscyB3ZWJzaXRlOiBbR2V0IHN0YXJ0ZWQgd2l0aCBUaWR5bW9kZWxzXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy9zdGFydC8pDQoNCi0gICBNYXggS3VobiBhbmQgSnVsaWEgU2lsZ2UsIFsqVGlkeSBNb2RlbGluZyB3aXRoIFIqXShodHRwczovL3d3dy50bXdyLm9yZy8pKi4qDQoNCiMjIyMjIyAqKlRIQU5LIFlPVSBUTzoqKg0KDQpbQWxsaXNvbiBIb3JzdF0oaHR0cHM6Ly90d2l0dGVyLmNvbS9hbGxpc29uX2hvcnN0P2xhbmc9ZW4pIGZvciBjcmVhdGluZyB0aGUgYW1hemluZyBpbGx1c3RyYXRpb25zIHRoYXQgbWFrZSBSIG1vcmUgd2VsY29taW5nIGFuZCBlbmdhZ2luZy4gRmluZCBtb3JlIGlsbHVzdHJhdGlvbnMgYXQgaGVyIFtnYWxsZXJ5XShodHRwczovL3d3dy5nb29nbGUuY29tL3VybD9xPWh0dHBzOi8vZ2l0aHViLmNvbS9hbGxpc29uaG9yc3Qvc3RhdHMtaWxsdXN0cmF0aW9ucyZzYT1EJnNvdXJjZT1lZGl0b3JzJnVzdD0xNjI2MzgwNzcyNTMwMDAwJnVzZz1BT3ZWYXczemNmeUNpekZRWnBrU0x6eGlpUUVNKS4NCg==