Cuisine classifiers 1

In this lesson, we’ll explore a variety of classifiers to predict a given national cuisine based on a group of ingredients. While doing so, we’ll learn more about some of the ways that algorithms can be leveraged for classification tasks.

Preparation

This lesson builds up on our previous lesson where we:

  • Made a gentle introduction to classifications using a dataset about all the brilliant cuisines of Asia and India 😋.

  • Explored some dplyr verbs to prep and clean our data.

  • Made beautiful visualizations using ggplot2.

  • Demonstrated how to deal with imbalanced data by preprocessing it using recipes.

  • Demonstrated how to prep and bake our recipe to confirm that it will work as supposed to.

Prerequisite

For this lesson, we’ll require the following packages to clean, prep and visualize our data:

  • 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.

  • DataExplorer: The DataExplorer package is meant to simplify and automate EDA process and report generation.

  • themis: The themis package provides Extra Recipes Steps for Dealing with Unbalanced Data.

  • nnet: The nnet package provides functions for estimating feed-forward neural networks with a single hidden layer, and for multinomial logistic regression models.

You can have them installed as:

install.packages(c("tidyverse", "tidymodels", "DataExplorer", "here"))

Alternatively, 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, DataExplorer, themis, here)

Now, let’s hit the ground running!

1. Split the data into training and test sets.

We’ll start by picking a few steps from our previous lesson.

Drop the most common ingredients that create confusion between distinct cuisines, using dplyr::select().

Everyone loves rice, garlic and ginger!

# Load the original cuisines data
df <- read_csv(file = "https://raw.githubusercontent.com/microsoft/ML-For-Beginners/main/4-Classification/data/cuisines.csv")
## New names:
## Rows: 2448 Columns: 385
## ── Column specification
## ──────────────────────────────────────────────────────── Delimiter: "," chr
## (1): cuisine dbl (384): ...1, almond, angelica, anise, anise_seed, apple,
## apple_brandy, a...
## ℹ Use `spec()` to retrieve the full column specification for this data. ℹ
## Specify the column types or set `show_col_types = FALSE` to quiet this message.
## • `` -> `...1`
# Drop id column, rice, garlic and ginger from our original data set
df_select <- df %>% 
  select(-c(1, rice, garlic, ginger)) %>%
  # Encode cuisine column as categorical
  mutate(cuisine = factor(cuisine))

# Display new data set
df_select %>% 
  slice_head(n = 5)
# Display distribution of cuisines
df_select %>% 
  count(cuisine) %>% 
  arrange(desc(n))

Perfect! Now, time to split the data such that 70% of the data goes to training and 30% goes to testing. We’ll also apply a stratification technique when splitting the data to maintain the proportion of each cuisine in the training and validation datasets.

rsample, a package in Tidymodels, provides infrastructure for efficient data splitting and resampling:

# Load the core Tidymodels packages into R session
library(tidymodels)

# Create split specification
set.seed(2056)
cuisines_split <- initial_split(data = df_select,
                                strata = cuisine,
                                prop = 0.7)

# Extract the data in each split
cuisines_train <- training(cuisines_split)
cuisines_test <- testing(cuisines_split)

# Print the number of cases in each split
cat("Training cases: ", nrow(cuisines_train), "\n",
    "Test cases: ", nrow(cuisines_test), sep = "")
## Training cases: 1712
## Test cases: 736
# Display the first few rows of the training set
cuisines_train %>% 
  slice_head(n = 5)
# Display distribution of cuisines in the training set
cuisines_train %>% 
  count(cuisine) %>% 
  arrange(desc(n))

2. Deal with imbalanced data

As you might have noticed in the original data set as well as in our training set, there is quite an unequal distribution in the number of cuisines. Korean cuisines are almost 3 times Thai cuisines. Imbalanced data often has negative effects on the model performance. Many models perform best when the number of observations is equal and, thus, tend to struggle with unbalanced data.

There are majorly two ways of dealing with imbalanced data sets:

  • adding observations to the minority class: Over-sampling e.g using a SMOTE algorithm which synthetically generates new examples of the minority class using nearest neighbors of these cases.

  • removing observations from majority class: Under-sampling

In our previous lesson, we demonstrated how to deal with imbalanced data sets using a recipe. A recipe can be thought of as a blueprint that describes what steps should be applied to a data set in order to get it ready for data analysis. In our case, we want to have an equal distribution in the number of our cuisines for our training set. Let’s get right into it.

# Load themis package for dealing with imbalanced data
library(themis)

# Create a recipe for preprocessing training data
cuisines_recipe <- recipe(cuisine ~ ., data = cuisines_train) %>% 
  step_smote(cuisine)

# Print recipe
cuisines_recipe
## 
## ── Recipe ──────────────────────────────────────────────────────────────────────
## 
## ── Inputs
## Number of variables by role
## outcome:     1
## predictor: 380
## 
## ── Operations
## • SMOTE based on: cuisine

You can of course go ahead and confirm (using prep+bake) that the recipe will work as you expect it - all the cuisine labels having 559 observations.

Since we’ll be using this recipe as a preprocessor for modeling, a workflow() will do all the prep and bake for us, so we won’t have to manually estimate the recipe.

Now we are ready to train a model 👩‍💻👨‍💻!

3. Choosing your classifier

Artwork by @allison_horst
Artwork by @allison_horst

Now we have to decide which algorithm to use for the job 🤔.

In Tidymodels, the parsnip package provides consistent interface for working with models across different engines (packages). Please see the parsnip documentation to explore model types & engines and their corresponding model arguments. The variety is quite bewildering at first sight. For instance, the following methods all include classification techniques:

  • C5.0 Rule-Based Classification Models

  • Flexible Discriminant Models

  • Linear Discriminant Models

  • Regularized Discriminant Models

  • Logistic Regression Models

  • Multinomial Regression Models

  • Naive Bayes Models

  • Support Vector Machines

  • Nearest Neighbors

  • Decision Trees

  • Ensemble methods

  • Neural Networks

The list goes on!

What classifier to go with?

So, which classifier should you choose? Often, running through several and looking for a good result is a way to test.

AutoML solves this problem neatly by running these comparisons in the cloud, allowing you to choose the best algorithm for your data. Try it here

Also the choice of classifier depends on our problem. For instance, when the outcome can be categorized into more than two classes, like in our case, you must use a multiclass classification algorithm as opposed to binary classification.

A better approach

A better way than wildly guessing, however, is to follow the ideas on this downloadable ML Cheat sheet. Here, we discover that, for our multiclass problem, we have some choices:

A section of Microsoft’s Algorithm Cheat Sheet, detailing multiclass classification options
A section of Microsoft’s Algorithm Cheat Sheet, detailing multiclass classification options

Reasoning

Let’s see if we can reason our way through different approaches given the constraints we have:

  • Deep Neural networks are too heavy. Given our clean, but minimal dataset, and the fact that we are running training locally via notebooks, deep neural networks are too heavyweight for this task.

  • No two-class classifier. We do not use a two-class classifier, so that rules out one-vs-all.

  • Decision tree or logistic regression could work. A decision tree might work, or multinomial regression/multiclass logistic regression for multiclass data.

  • Multiclass Boosted Decision Trees solve a different problem. The multiclass boosted decision tree is most suitable for nonparametric tasks, e.g. tasks designed to build rankings, so it is not useful for us.

Also, normally before embarking on more complex machine learning models e.g ensemble methods, it’s a good idea to build the simplest possible model to get an idea of what is going on. So for this lesson, we’ll start with a multinomial logistic regression model.

Logistic regression is a technique used when the outcome variable is categorical (or nominal). For Binary logistic regression the number of outcome variables is two, whereas the number of outcome variables for multinomial logistic regression is more than two. See Advanced Regression Methods for further reading.

4. Train and evaluate a Multinomial logistic regression model.

In Tidymodels, parsnip::multinom_reg(), defines a model that uses linear predictors to predict multiclass data using the multinomial distribution. See ?multinom_reg() for the different ways/engines you can use to fit this model.

For this example, we’ll fit a Multinomial regression model via the default nnet engine.

I picked a value for penalty sort of randomly. There are better ways to choose this value that is, by using resampling and tuning the model which we’ll discuss later.

See Tidymodels: Get Started in case you want to learn more on how to tune model hyperparameters.

# Create a multinomial regression model specification
mr_spec <- multinom_reg(penalty = 1) %>% 
  set_engine("nnet", MaxNWts = 2086) %>% 
  set_mode("classification")

# Print model specification
mr_spec
## Multinomial Regression Model Specification (classification)
## 
## Main Arguments:
##   penalty = 1
## 
## Engine-Specific Arguments:
##   MaxNWts = 2086
## 
## Computational engine: nnet

Great 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 then fit the model on the preprocessed data and also allow for potential post-processing activities. 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!📦

# Bundle recipe and model specification
mr_wf <- workflow() %>% 
  add_recipe(cuisines_recipe) %>% 
  add_model(mr_spec)

# Print out workflow
mr_wf
## ══ Workflow ════════════════════════════════════════════════════════════════════
## Preprocessor: Recipe
## Model: multinom_reg()
## 
## ── Preprocessor ────────────────────────────────────────────────────────────────
## 1 Recipe Step
## 
## • step_smote()
## 
## ── Model ───────────────────────────────────────────────────────────────────────
## Multinomial Regression Model Specification (classification)
## 
## Main Arguments:
##   penalty = 1
## 
## Engine-Specific Arguments:
##   MaxNWts = 2086
## 
## Computational engine: nnet

Workflows 👌👌! A workflow() can be fit in much the same way a model can. So, time to train a model!

# Train a multinomial regression model
mr_fit <- fit(object = mr_wf, data = cuisines_train)

mr_fit
## ══ Workflow [trained] ══════════════════════════════════════════════════════════
## Preprocessor: Recipe
## Model: multinom_reg()
## 
## ── Preprocessor ────────────────────────────────────────────────────────────────
## 1 Recipe Step
## 
## • step_smote()
## 
## ── Model ───────────────────────────────────────────────────────────────────────
## Call:
## nnet::multinom(formula = ..y ~ ., data = data, decay = ~1, MaxNWts = ~2086, 
##     trace = FALSE)
## 
## Coefficients:
##          (Intercept)     almond angelica         anise anise_seed       apple
## indian    0.19723325  0.2409661        0 -5.004955e-05 -0.1657635 -0.05769734
## japanese  0.13961959 -0.6262400        0 -1.169155e-04 -0.4893596 -0.08585717
## korean    0.22377347 -0.1833485        0 -5.560395e-05 -0.2489401 -0.15657804
## thai     -0.04336577 -0.6106258        0  4.903828e-04 -0.5782866  0.63451105
##          apple_brandy     apricot armagnac   artemisia artichoke   asparagus
## indian              0  0.37042636        0 -0.09122797         0 -0.27181970
## japanese            0  0.28895643        0 -0.12651100         0  0.14054037
## korean              0 -0.07981259        0  0.55756709         0 -0.66979948
## thai                0 -0.33160904        0 -0.10725182         0 -0.02602152
##              avocado       bacon baked_potato balm     banana     barley
## indian   -0.46624197  0.16008055            0    0 -0.2838796  0.2230625
## japanese  0.90341344  0.02932727            0    0 -0.4142787  2.0953906
## korean   -0.06925382 -0.35804134            0    0 -0.2686963 -0.7233404
## thai     -0.21473955 -0.75594439            0    0  0.6784880 -0.4363320
##          bartlett_pear      basil        bay       bean         beech
## indian               0 -0.7128756  0.1011587 -0.8777275 -0.0004380795
## japanese             0  0.1288697  0.9425626 -0.2380748  0.3373437611
## korean               0 -0.2445193 -0.4744318 -0.8957870 -0.0048784496
## thai                 0  1.5365848  0.1333256  0.2196970 -0.0113078024
##                beef beef_broth   beef_liver         beer        beet
## indian   -0.7985278  0.2430186 -0.035598065 -0.002173738  0.01005813
## japanese  0.2241875 -0.3653020 -0.139551027  0.128905553  0.04923911
## korean    0.5366515 -0.6153237  0.213455197 -0.010828645  0.27325423
## thai      0.1570012 -0.9364154 -0.008032213 -0.035063746 -0.28279823
##          bell_pepper bergamot       berry bitter_orange black_bean
## indian    0.49074330        0  0.58947607   0.191256164 -0.1945233
## japanese  0.09074167        0 -0.25917977  -0.118915977 -0.3442400
## korean   -0.57876763        0 -0.07874180  -0.007729435 -0.5220672
## thai      0.92554006        0 -0.07210196  -0.002983296 -0.4614426
##          black_currant black_mustard_seed_oil black_pepper black_raspberry
## indian               0             0.38935801   -0.4453495               0
## japanese             0            -0.05452887   -0.5440869               0
## korean               0            -0.03929970    0.8025454               0
## thai                 0            -0.21498372   -0.9854806               0
##          black_sesame_seed  black_tea   blackberry blackberry_brandy
## indian          -0.2759246  0.3079977  0.191256164                 0
## japanese        -0.6101687 -0.1671913 -0.118915977                 0
## korean           1.5197674 -0.3036261 -0.007729435                 0
## thai            -0.1755656 -0.1487033 -0.002983296                 0
##          blue_cheese    blueberry   bone_oil bourbon_whiskey      brandy
## indian             0  0.216164294 -0.2276744               0  0.22427587
## japanese           0 -0.119186087  0.3913019               0 -0.15595599
## korean             0 -0.007821986  0.2854487               0 -0.02562342
## thai               0 -0.004947048 -0.0253658               0 -0.05715244
## 
## ...
## and 308 more lines.

The output shows the coefficients that the model learned during training.

Evaluate the Trained Model

It’s time to see how the model performed 📏 by evaluating it on a test set! Let’s begin by making predictions on the test set.

# Make predictions on the test set
results <- cuisines_test %>% select(cuisine) %>% 
  bind_cols(mr_fit %>% predict(new_data = cuisines_test))

# Print out results
results %>% 
  slice_head(n = 5)

Great job! In Tidymodels, evaluating model performance can be done using yardstick - a package used to measure the effectiveness of models using performance metrics. As we did in our logistic regression lesson, let’s begin by computing a confusion matrix.

# Confusion matrix for categorical data
conf_mat(data = results, truth = cuisine, estimate = .pred_class)
##           Truth
## Prediction chinese indian japanese korean thai
##   chinese       83      1        8     15   10
##   indian         4    163        1      2    6
##   japanese      21      5       73     25    1
##   korean        15      0       11    191    0
##   thai          10     11        3      7   70

When dealing with multiple classes, it’s generally more intuitive to visualize this as a heat map, like this:

update_geom_defaults(geom = "tile", new = list(color = "black", alpha = 0.7))
# Visualize confusion matrix
results %>% 
  conf_mat(cuisine, .pred_class) %>% 
  autoplot(type = "heatmap")

The darker squares in the confusion matrix plot indicate high numbers of cases, and you can hopefully see a diagonal line of darker squares indicating cases where the predicted and actual label are the same.

Let’s now calculate summary statistics for the confusion matrix.

# Summary stats for confusion matrix
conf_mat(data = results, truth = cuisine, estimate = .pred_class) %>% summary()

If we narrow down to some metrics such as accuracy, sensitivity, ppv, we are not badly off for a start 🥳!

4. Digging Deeper

Let’s ask one subtle question: What criteria is used to settle for a given type of cuisine as the predicted outcome?

Well, Statistical machine learning algorithms, like logistic regression, are based on probability; so what actually gets predicted by a classifier is a probability distribution over a set of possible outcomes. The class with the highest probability is then chosen as the most likely outcome for the given observations.

Let’s see this in action by making both hard class predictions and probabilities.

# Make hard class prediction and probabilities
results_prob <- cuisines_test %>%
  select(cuisine) %>% 
  bind_cols(mr_fit %>% predict(new_data = cuisines_test)) %>% 
  bind_cols(mr_fit %>% predict(new_data = cuisines_test, type = "prob"))

# Print out results
results_prob %>% 
  slice_head(n = 5)

Much better!

✅ Can you explain why the model is pretty sure that the first observation is Thai?

🚀Challenge

In this lesson, you used your cleaned data to build a machine learning model that can predict a national cuisine based on a series of ingredients. Take some time to read through the many options Tidymodels provides to classify data and other ways to fit multinomial regression.

THANK YOU TO:

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

Cassie Breviu and Jen Looper for creating the original Python version of this module ♥️

Happy Learning,

Eric, Gold Microsoft Learn Student Ambassador.

LS0tCnRpdGxlOiAnQnVpbGQgYSBjbGFzc2lmaWNhdGlvbiBtb2RlbDogRGVsaWNpb3VzIEFzaWFuIGFuZCBJbmRpYW4gQ3Vpc2luZXMnCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgICB0aGVtZTogZmxhdGx5CiAgICBoaWdobGlnaHQ6IGJyZWV6ZWRhcmsKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHllcwogICAgY29kZV9kb3dubG9hZDogeWVzCi0tLQoKIyMgQ3Vpc2luZSBjbGFzc2lmaWVycyAxCgpJbiB0aGlzIGxlc3Nvbiwgd2UnbGwgZXhwbG9yZSBhIHZhcmlldHkgb2YgY2xhc3NpZmllcnMgdG8gKnByZWRpY3QgYSBnaXZlbiBuYXRpb25hbCBjdWlzaW5lIGJhc2VkIG9uIGEgZ3JvdXAgb2YgaW5ncmVkaWVudHMuKiBXaGlsZSBkb2luZyBzbywgd2UnbGwgbGVhcm4gbW9yZSBhYm91dCBzb21lIG9mIHRoZSB3YXlzIHRoYXQgYWxnb3JpdGhtcyBjYW4gYmUgbGV2ZXJhZ2VkIGZvciBjbGFzc2lmaWNhdGlvbiB0YXNrcy4KCiMjIyBbKipQcmUtbGVjdHVyZSBxdWl6KipdKGh0dHBzOi8vZ3JheS1zYW5kLTA3YTEwZjQwMy4xLmF6dXJlc3RhdGljYXBwcy5uZXQvcXVpei8yMS8pCgojIyMgKipQcmVwYXJhdGlvbioqCgpUaGlzIGxlc3NvbiBidWlsZHMgdXAgb24gb3VyIFtwcmV2aW91cyBsZXNzb25dKGh0dHBzOi8vZ2l0aHViLmNvbS9taWNyb3NvZnQvTUwtRm9yLUJlZ2lubmVycy9ibG9iL21haW4vNC1DbGFzc2lmaWNhdGlvbi8xLUludHJvZHVjdGlvbi9zb2x1dGlvbi9SL2xlc3Nvbl8xMC5odG1sKSB3aGVyZSB3ZToKCi0gICBNYWRlIGEgZ2VudGxlIGludHJvZHVjdGlvbiB0byBjbGFzc2lmaWNhdGlvbnMgdXNpbmcgYSBkYXRhc2V0IGFib3V0IGFsbCB0aGUgYnJpbGxpYW50IGN1aXNpbmVzIG9mIEFzaWEgYW5kIEluZGlhIPCfmIsuCgotICAgRXhwbG9yZWQgc29tZSBbZHBseXIgdmVyYnNdKGh0dHBzOi8vZHBseXIudGlkeXZlcnNlLm9yZy8pIHRvIHByZXAgYW5kIGNsZWFuIG91ciBkYXRhLgoKLSAgIE1hZGUgYmVhdXRpZnVsIHZpc3VhbGl6YXRpb25zIHVzaW5nIGdncGxvdDIuCgotICAgRGVtb25zdHJhdGVkIGhvdyB0byBkZWFsIHdpdGggaW1iYWxhbmNlZCBkYXRhIGJ5IHByZXByb2Nlc3NpbmcgaXQgdXNpbmcgW3JlY2lwZXNdKGh0dHBzOi8vcmVjaXBlcy50aWR5bW9kZWxzLm9yZy9hcnRpY2xlcy9TaW1wbGVfRXhhbXBsZS5odG1sKS4KCi0gICBEZW1vbnN0cmF0ZWQgaG93IHRvIGBwcmVwYCBhbmQgYGJha2VgIG91ciByZWNpcGUgdG8gY29uZmlybSB0aGF0IGl0IHdpbGwgd29yayBhcyBzdXBwb3NlZCB0by4KCiMjIyMgKipQcmVyZXF1aXNpdGUqKgoKRm9yIHRoaXMgbGVzc29uLCB3ZSdsbCByZXF1aXJlIHRoZSBmb2xsb3dpbmcgcGFja2FnZXMgdG8gY2xlYW4sIHByZXAgYW5kIHZpc3VhbGl6ZSBvdXIgZGF0YToKCi0gICBgdGlkeXZlcnNlYDogVGhlIFt0aWR5dmVyc2VdKGh0dHBzOi8vd3d3LnRpZHl2ZXJzZS5vcmcvKSBpcyBhIFtjb2xsZWN0aW9uIG9mIFIgcGFja2FnZXNdKGh0dHBzOi8vd3d3LnRpZHl2ZXJzZS5vcmcvcGFja2FnZXMpIGRlc2lnbmVkIHRvIG1ha2VzIGRhdGEgc2NpZW5jZSBmYXN0ZXIsIGVhc2llciBhbmQgbW9yZSBmdW4hCgotICAgYHRpZHltb2RlbHNgOiBUaGUgW3RpZHltb2RlbHNdKGh0dHBzOi8vd3d3LnRpZHltb2RlbHMub3JnLykgZnJhbWV3b3JrIGlzIGEgW2NvbGxlY3Rpb24gb2YgcGFja2FnZXNdKGh0dHBzOi8vd3d3LnRpZHltb2RlbHMub3JnL3BhY2thZ2VzLykgZm9yIG1vZGVsaW5nIGFuZCBtYWNoaW5lIGxlYXJuaW5nLgoKLSAgIGBEYXRhRXhwbG9yZXJgOiBUaGUgW0RhdGFFeHBsb3JlciBwYWNrYWdlXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvRGF0YUV4cGxvcmVyL3ZpZ25ldHRlcy9kYXRhZXhwbG9yZXItaW50cm8uaHRtbCkgaXMgbWVhbnQgdG8gc2ltcGxpZnkgYW5kIGF1dG9tYXRlIEVEQSBwcm9jZXNzIGFuZCByZXBvcnQgZ2VuZXJhdGlvbi4KCi0gICBgdGhlbWlzYDogVGhlIFt0aGVtaXMgcGFja2FnZV0oaHR0cHM6Ly90aGVtaXMudGlkeW1vZGVscy5vcmcvKSBwcm92aWRlcyBFeHRyYSBSZWNpcGVzIFN0ZXBzIGZvciBEZWFsaW5nIHdpdGggVW5iYWxhbmNlZCBEYXRhLgoKLSAgIGBubmV0YDogVGhlIFtubmV0IHBhY2thZ2VdKGh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9ubmV0L25uZXQucGRmKSBwcm92aWRlcyBmdW5jdGlvbnMgZm9yIGVzdGltYXRpbmcgZmVlZC1mb3J3YXJkIG5ldXJhbCBuZXR3b3JrcyB3aXRoIGEgc2luZ2xlIGhpZGRlbiBsYXllciwgYW5kIGZvciBtdWx0aW5vbWlhbCBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVscy4KCllvdSBjYW4gaGF2ZSB0aGVtIGluc3RhbGxlZCBhczoKCmBpbnN0YWxsLnBhY2thZ2VzKGMoInRpZHl2ZXJzZSIsICJ0aWR5bW9kZWxzIiwgIkRhdGFFeHBsb3JlciIsICJoZXJlIikpYAoKQWx0ZXJuYXRpdmVseSwgdGhlIHNjcmlwdCBiZWxvdyBjaGVja3Mgd2hldGhlciB5b3UgaGF2ZSB0aGUgcGFja2FnZXMgcmVxdWlyZWQgdG8gY29tcGxldGUgdGhpcyBtb2R1bGUgYW5kIGluc3RhbGxzIHRoZW0gZm9yIHlvdSBpbiBjYXNlIHRoZXkgYXJlIG1pc3NpbmcuCgpgYGB7ciwgbWVzc2FnZT1GLCB3YXJuaW5nPUZ9CnN1cHByZXNzV2FybmluZ3MoaWYgKCFyZXF1aXJlKCJwYWNtYW4iKSlpbnN0YWxsLnBhY2thZ2VzKCJwYWNtYW4iKSkKCnBhY21hbjo6cF9sb2FkKHRpZHl2ZXJzZSwgdGlkeW1vZGVscywgRGF0YUV4cGxvcmVyLCB0aGVtaXMsIGhlcmUpCmBgYAoKTm93LCBsZXQncyBoaXQgdGhlIGdyb3VuZCBydW5uaW5nIQoKIyMgMS4gU3BsaXQgdGhlIGRhdGEgaW50byB0cmFpbmluZyBhbmQgdGVzdCBzZXRzLgoKV2UnbGwgc3RhcnQgYnkgcGlja2luZyBhIGZldyBzdGVwcyBmcm9tIG91ciBwcmV2aW91cyBsZXNzb24uCgojIyMgRHJvcCB0aGUgbW9zdCBjb21tb24gaW5ncmVkaWVudHMgdGhhdCBjcmVhdGUgY29uZnVzaW9uIGJldHdlZW4gZGlzdGluY3QgY3Vpc2luZXMsIHVzaW5nIGBkcGx5cjo6c2VsZWN0KClgLgoKRXZlcnlvbmUgbG92ZXMgcmljZSwgZ2FybGljIGFuZCBnaW5nZXIhCgpgYGB7ciByZWNhcF9kcm9wfQojIExvYWQgdGhlIG9yaWdpbmFsIGN1aXNpbmVzIGRhdGEKZGYgPC0gcmVhZF9jc3YoZmlsZSA9ICJodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vbWljcm9zb2Z0L01MLUZvci1CZWdpbm5lcnMvbWFpbi80LUNsYXNzaWZpY2F0aW9uL2RhdGEvY3Vpc2luZXMuY3N2IikKCiMgRHJvcCBpZCBjb2x1bW4sIHJpY2UsIGdhcmxpYyBhbmQgZ2luZ2VyIGZyb20gb3VyIG9yaWdpbmFsIGRhdGEgc2V0CmRmX3NlbGVjdCA8LSBkZiAlPiUgCiAgc2VsZWN0KC1jKDEsIHJpY2UsIGdhcmxpYywgZ2luZ2VyKSkgJT4lCiAgIyBFbmNvZGUgY3Vpc2luZSBjb2x1bW4gYXMgY2F0ZWdvcmljYWwKICBtdXRhdGUoY3Vpc2luZSA9IGZhY3RvcihjdWlzaW5lKSkKCiMgRGlzcGxheSBuZXcgZGF0YSBzZXQKZGZfc2VsZWN0ICU+JSAKICBzbGljZV9oZWFkKG4gPSA1KQoKIyBEaXNwbGF5IGRpc3RyaWJ1dGlvbiBvZiBjdWlzaW5lcwpkZl9zZWxlY3QgJT4lIAogIGNvdW50KGN1aXNpbmUpICU+JSAKICBhcnJhbmdlKGRlc2MobikpCmBgYAoKUGVyZmVjdCEgTm93LCB0aW1lIHRvIHNwbGl0IHRoZSBkYXRhIHN1Y2ggdGhhdCA3MCUgb2YgdGhlIGRhdGEgZ29lcyB0byB0cmFpbmluZyBhbmQgMzAlIGdvZXMgdG8gdGVzdGluZy4gV2UnbGwgYWxzbyBhcHBseSBhIGBzdHJhdGlmaWNhdGlvbmAgdGVjaG5pcXVlIHdoZW4gc3BsaXR0aW5nIHRoZSBkYXRhIHRvIGBtYWludGFpbiB0aGUgcHJvcG9ydGlvbiBvZiBlYWNoIGN1aXNpbmVgIGluIHRoZSB0cmFpbmluZyBhbmQgdmFsaWRhdGlvbiBkYXRhc2V0cy4KCltyc2FtcGxlXShodHRwczovL3JzYW1wbGUudGlkeW1vZGVscy5vcmcvKSwgYSBwYWNrYWdlIGluIFRpZHltb2RlbHMsIHByb3ZpZGVzIGluZnJhc3RydWN0dXJlIGZvciBlZmZpY2llbnQgZGF0YSBzcGxpdHRpbmcgYW5kIHJlc2FtcGxpbmc6CgpgYGB7ciBkYXRhX3NwbGl0fQojIExvYWQgdGhlIGNvcmUgVGlkeW1vZGVscyBwYWNrYWdlcyBpbnRvIFIgc2Vzc2lvbgpsaWJyYXJ5KHRpZHltb2RlbHMpCgojIENyZWF0ZSBzcGxpdCBzcGVjaWZpY2F0aW9uCnNldC5zZWVkKDIwNTYpCmN1aXNpbmVzX3NwbGl0IDwtIGluaXRpYWxfc3BsaXQoZGF0YSA9IGRmX3NlbGVjdCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdHJhdGEgPSBjdWlzaW5lLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByb3AgPSAwLjcpCgojIEV4dHJhY3QgdGhlIGRhdGEgaW4gZWFjaCBzcGxpdApjdWlzaW5lc190cmFpbiA8LSB0cmFpbmluZyhjdWlzaW5lc19zcGxpdCkKY3Vpc2luZXNfdGVzdCA8LSB0ZXN0aW5nKGN1aXNpbmVzX3NwbGl0KQoKIyBQcmludCB0aGUgbnVtYmVyIG9mIGNhc2VzIGluIGVhY2ggc3BsaXQKY2F0KCJUcmFpbmluZyBjYXNlczogIiwgbnJvdyhjdWlzaW5lc190cmFpbiksICJcbiIsCiAgICAiVGVzdCBjYXNlczogIiwgbnJvdyhjdWlzaW5lc190ZXN0KSwgc2VwID0gIiIpCgojIERpc3BsYXkgdGhlIGZpcnN0IGZldyByb3dzIG9mIHRoZSB0cmFpbmluZyBzZXQKY3Vpc2luZXNfdHJhaW4gJT4lIAogIHNsaWNlX2hlYWQobiA9IDUpCgoKIyBEaXNwbGF5IGRpc3RyaWJ1dGlvbiBvZiBjdWlzaW5lcyBpbiB0aGUgdHJhaW5pbmcgc2V0CmN1aXNpbmVzX3RyYWluICU+JSAKICBjb3VudChjdWlzaW5lKSAlPiUgCiAgYXJyYW5nZShkZXNjKG4pKQoKCmBgYAoKIyMgMi4gRGVhbCB3aXRoIGltYmFsYW5jZWQgZGF0YQoKQXMgeW91IG1pZ2h0IGhhdmUgbm90aWNlZCBpbiB0aGUgb3JpZ2luYWwgZGF0YSBzZXQgYXMgd2VsbCBhcyBpbiBvdXIgdHJhaW5pbmcgc2V0LCB0aGVyZSBpcyBxdWl0ZSBhbiB1bmVxdWFsIGRpc3RyaWJ1dGlvbiBpbiB0aGUgbnVtYmVyIG9mIGN1aXNpbmVzLiBLb3JlYW4gY3Vpc2luZXMgYXJlICphbG1vc3QqIDMgdGltZXMgVGhhaSBjdWlzaW5lcy4gSW1iYWxhbmNlZCBkYXRhIG9mdGVuIGhhcyBuZWdhdGl2ZSBlZmZlY3RzIG9uIHRoZSBtb2RlbCBwZXJmb3JtYW5jZS4gTWFueSBtb2RlbHMgcGVyZm9ybSBiZXN0IHdoZW4gdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgaXMgZXF1YWwgYW5kLCB0aHVzLCB0ZW5kIHRvIHN0cnVnZ2xlIHdpdGggdW5iYWxhbmNlZCBkYXRhLgoKVGhlcmUgYXJlIG1ham9ybHkgdHdvIHdheXMgb2YgZGVhbGluZyB3aXRoIGltYmFsYW5jZWQgZGF0YSBzZXRzOgoKLSAgIGFkZGluZyBvYnNlcnZhdGlvbnMgdG8gdGhlIG1pbm9yaXR5IGNsYXNzOiBgT3Zlci1zYW1wbGluZ2AgZS5nIHVzaW5nIGEgU01PVEUgYWxnb3JpdGhtIHdoaWNoIHN5bnRoZXRpY2FsbHkgZ2VuZXJhdGVzIG5ldyBleGFtcGxlcyBvZiB0aGUgbWlub3JpdHkgY2xhc3MgdXNpbmcgbmVhcmVzdCBuZWlnaGJvcnMgb2YgdGhlc2UgY2FzZXMuCgotICAgcmVtb3Zpbmcgb2JzZXJ2YXRpb25zIGZyb20gbWFqb3JpdHkgY2xhc3M6IGBVbmRlci1zYW1wbGluZ2AKCkluIG91ciBwcmV2aW91cyBsZXNzb24sIHdlIGRlbW9uc3RyYXRlZCBob3cgdG8gZGVhbCB3aXRoIGltYmFsYW5jZWQgZGF0YSBzZXRzIHVzaW5nIGEgYHJlY2lwZWAuIEEgcmVjaXBlIGNhbiBiZSB0aG91Z2h0IG9mIGFzIGEgYmx1ZXByaW50IHRoYXQgZGVzY3JpYmVzIHdoYXQgc3RlcHMgc2hvdWxkIGJlIGFwcGxpZWQgdG8gYSBkYXRhIHNldCBpbiBvcmRlciB0byBnZXQgaXQgcmVhZHkgZm9yIGRhdGEgYW5hbHlzaXMuIEluIG91ciBjYXNlLCB3ZSB3YW50IHRvIGhhdmUgYW4gZXF1YWwgZGlzdHJpYnV0aW9uIGluIHRoZSBudW1iZXIgb2Ygb3VyIGN1aXNpbmVzIGZvciBvdXIgYHRyYWluaW5nIHNldGAuIExldCdzIGdldCByaWdodCBpbnRvIGl0LgoKYGBge3IgcmVjYXBfYmFsYW5jZX0KIyBMb2FkIHRoZW1pcyBwYWNrYWdlIGZvciBkZWFsaW5nIHdpdGggaW1iYWxhbmNlZCBkYXRhCmxpYnJhcnkodGhlbWlzKQoKIyBDcmVhdGUgYSByZWNpcGUgZm9yIHByZXByb2Nlc3NpbmcgdHJhaW5pbmcgZGF0YQpjdWlzaW5lc19yZWNpcGUgPC0gcmVjaXBlKGN1aXNpbmUgfiAuLCBkYXRhID0gY3Vpc2luZXNfdHJhaW4pICU+JSAKICBzdGVwX3Ntb3RlKGN1aXNpbmUpCgojIFByaW50IHJlY2lwZQpjdWlzaW5lc19yZWNpcGUKCmBgYAoKWW91IGNhbiBvZiBjb3Vyc2UgZ28gYWhlYWQgYW5kIGNvbmZpcm0gKHVzaW5nIHByZXArYmFrZSkgdGhhdCB0aGUgcmVjaXBlIHdpbGwgd29yayBhcyB5b3UgZXhwZWN0IGl0IC0gYWxsIHRoZSBjdWlzaW5lIGxhYmVscyBoYXZpbmcgYDU1OWAgb2JzZXJ2YXRpb25zLgoKU2luY2Ugd2UnbGwgYmUgdXNpbmcgdGhpcyByZWNpcGUgYXMgYSBwcmVwcm9jZXNzb3IgZm9yIG1vZGVsaW5nLCBhIGB3b3JrZmxvdygpYCB3aWxsIGRvIGFsbCB0aGUgcHJlcCBhbmQgYmFrZSBmb3IgdXMsIHNvIHdlIHdvbid0IGhhdmUgdG8gbWFudWFsbHkgZXN0aW1hdGUgdGhlIHJlY2lwZS4KCk5vdyB3ZSBhcmUgcmVhZHkgdG8gdHJhaW4gYSBtb2RlbCDwn5Gp4oCN8J+Su/CfkajigI3wn5K7IQoKIyMgMy4gQ2hvb3NpbmcgeW91ciBjbGFzc2lmaWVyCgohW0FydHdvcmsgYnkgXEBhbGxpc29uX2hvcnN0XSguLi8uLi9pbWFnZXMvcGFyc25pcC5qcGcpe3dpZHRoPSI2MDAifQoKTm93IHdlIGhhdmUgdG8gZGVjaWRlIHdoaWNoIGFsZ29yaXRobSB0byB1c2UgZm9yIHRoZSBqb2Ig8J+klC4KCkluIFRpZHltb2RlbHMsIHRoZSBbYHBhcnNuaXAgcGFja2FnZWBdKGh0dHBzOi8vcGFyc25pcC50aWR5bW9kZWxzLm9yZy9pbmRleC5odG1sKSBwcm92aWRlcyBjb25zaXN0ZW50IGludGVyZmFjZSBmb3Igd29ya2luZyB3aXRoIG1vZGVscyBhY3Jvc3MgZGlmZmVyZW50IGVuZ2luZXMgKHBhY2thZ2VzKS4gUGxlYXNlIHNlZSB0aGUgcGFyc25pcCBkb2N1bWVudGF0aW9uIHRvIGV4cGxvcmUgW21vZGVsIHR5cGVzICYgZW5naW5lc10oaHR0cHM6Ly93d3cudGlkeW1vZGVscy5vcmcvZmluZC9wYXJzbmlwLyNtb2RlbHMpIGFuZCB0aGVpciBjb3JyZXNwb25kaW5nIFttb2RlbCBhcmd1bWVudHNdKGh0dHBzOi8vd3d3LnRpZHltb2RlbHMub3JnL2ZpbmQvcGFyc25pcC8jbW9kZWwtYXJncykuIFRoZSB2YXJpZXR5IGlzIHF1aXRlIGJld2lsZGVyaW5nIGF0IGZpcnN0IHNpZ2h0LiBGb3IgaW5zdGFuY2UsIHRoZSBmb2xsb3dpbmcgbWV0aG9kcyBhbGwgaW5jbHVkZSBjbGFzc2lmaWNhdGlvbiB0ZWNobmlxdWVzOgoKLSAgIEM1LjAgUnVsZS1CYXNlZCBDbGFzc2lmaWNhdGlvbiBNb2RlbHMKCi0gICBGbGV4aWJsZSBEaXNjcmltaW5hbnQgTW9kZWxzCgotICAgTGluZWFyIERpc2NyaW1pbmFudCBNb2RlbHMKCi0gICBSZWd1bGFyaXplZCBEaXNjcmltaW5hbnQgTW9kZWxzCgotICAgTG9naXN0aWMgUmVncmVzc2lvbiBNb2RlbHMKCi0gICBNdWx0aW5vbWlhbCBSZWdyZXNzaW9uIE1vZGVscwoKLSAgIE5haXZlIEJheWVzIE1vZGVscwoKLSAgIFN1cHBvcnQgVmVjdG9yIE1hY2hpbmVzCgotICAgTmVhcmVzdCBOZWlnaGJvcnMKCi0gICBEZWNpc2lvbiBUcmVlcwoKLSAgIEVuc2VtYmxlIG1ldGhvZHMKCi0gICBOZXVyYWwgTmV0d29ya3MKClRoZSBsaXN0IGdvZXMgb24hCgojIyMgKipXaGF0IGNsYXNzaWZpZXIgdG8gZ28gd2l0aD8qKgoKU28sIHdoaWNoIGNsYXNzaWZpZXIgc2hvdWxkIHlvdSBjaG9vc2U/IE9mdGVuLCBydW5uaW5nIHRocm91Z2ggc2V2ZXJhbCBhbmQgbG9va2luZyBmb3IgYSBnb29kIHJlc3VsdCBpcyBhIHdheSB0byB0ZXN0LgoKPiBBdXRvTUwgc29sdmVzIHRoaXMgcHJvYmxlbSBuZWF0bHkgYnkgcnVubmluZyB0aGVzZSBjb21wYXJpc29ucyBpbiB0aGUgY2xvdWQsIGFsbG93aW5nIHlvdSB0byBjaG9vc2UgdGhlIGJlc3QgYWxnb3JpdGhtIGZvciB5b3VyIGRhdGEuIFRyeSBpdCBbaGVyZV0oaHR0cHM6Ly9kb2NzLm1pY3Jvc29mdC5jb20vbGVhcm4vbW9kdWxlcy9hdXRvbWF0ZS1tb2RlbC1zZWxlY3Rpb24td2l0aC1henVyZS1hdXRvbWwvP1dULm1jX2lkPWFjYWRlbWljLTc3OTUyLWxlZXN0b3R0KQoKQWxzbyB0aGUgY2hvaWNlIG9mIGNsYXNzaWZpZXIgZGVwZW5kcyBvbiBvdXIgcHJvYmxlbS4gRm9yIGluc3RhbmNlLCB3aGVuIHRoZSBvdXRjb21lIGNhbiBiZSBjYXRlZ29yaXplZCBpbnRvIGBtb3JlIHRoYW4gdHdvIGNsYXNzZXNgLCBsaWtlIGluIG91ciBjYXNlLCB5b3UgbXVzdCB1c2UgYSBgbXVsdGljbGFzcyBjbGFzc2lmaWNhdGlvbiBhbGdvcml0aG1gIGFzIG9wcG9zZWQgdG8gYGJpbmFyeSBjbGFzc2lmaWNhdGlvbi5gCgojIyMgKipBIGJldHRlciBhcHByb2FjaCoqCgpBIGJldHRlciB3YXkgdGhhbiB3aWxkbHkgZ3Vlc3NpbmcsIGhvd2V2ZXIsIGlzIHRvIGZvbGxvdyB0aGUgaWRlYXMgb24gdGhpcyBkb3dubG9hZGFibGUgW01MIENoZWF0IHNoZWV0XShodHRwczovL2RvY3MubWljcm9zb2Z0LmNvbS9henVyZS9tYWNoaW5lLWxlYXJuaW5nL2FsZ29yaXRobS1jaGVhdC1zaGVldD9XVC5tY19pZD1hY2FkZW1pYy03Nzk1Mi1sZWVzdG90dCkuIEhlcmUsIHdlIGRpc2NvdmVyIHRoYXQsIGZvciBvdXIgbXVsdGljbGFzcyBwcm9ibGVtLCB3ZSBoYXZlIHNvbWUgY2hvaWNlczoKCiFbQSBzZWN0aW9uIG9mIE1pY3Jvc29mdCdzIEFsZ29yaXRobSBDaGVhdCBTaGVldCwgZGV0YWlsaW5nIG11bHRpY2xhc3MgY2xhc3NpZmljYXRpb24gb3B0aW9uc10oLi4vLi4vaW1hZ2VzL2NoZWF0c2hlZXQucG5nKXt3aWR0aD0iNTAwIn0KCiMjIyAqKlJlYXNvbmluZyoqCgpMZXQncyBzZWUgaWYgd2UgY2FuIHJlYXNvbiBvdXIgd2F5IHRocm91Z2ggZGlmZmVyZW50IGFwcHJvYWNoZXMgZ2l2ZW4gdGhlIGNvbnN0cmFpbnRzIHdlIGhhdmU6CgotICAgKipEZWVwIE5ldXJhbCBuZXR3b3JrcyBhcmUgdG9vIGhlYXZ5KiouIEdpdmVuIG91ciBjbGVhbiwgYnV0IG1pbmltYWwgZGF0YXNldCwgYW5kIHRoZSBmYWN0IHRoYXQgd2UgYXJlIHJ1bm5pbmcgdHJhaW5pbmcgbG9jYWxseSB2aWEgbm90ZWJvb2tzLCBkZWVwIG5ldXJhbCBuZXR3b3JrcyBhcmUgdG9vIGhlYXZ5d2VpZ2h0IGZvciB0aGlzIHRhc2suCgotICAgKipObyB0d28tY2xhc3MgY2xhc3NpZmllcioqLiBXZSBkbyBub3QgdXNlIGEgdHdvLWNsYXNzIGNsYXNzaWZpZXIsIHNvIHRoYXQgcnVsZXMgb3V0IG9uZS12cy1hbGwuCgotICAgKipEZWNpc2lvbiB0cmVlIG9yIGxvZ2lzdGljIHJlZ3Jlc3Npb24gY291bGQgd29yayoqLiBBIGRlY2lzaW9uIHRyZWUgbWlnaHQgd29yaywgb3IgbXVsdGlub21pYWwgcmVncmVzc2lvbi9tdWx0aWNsYXNzIGxvZ2lzdGljIHJlZ3Jlc3Npb24gZm9yIG11bHRpY2xhc3MgZGF0YS4KCi0gICAqKk11bHRpY2xhc3MgQm9vc3RlZCBEZWNpc2lvbiBUcmVlcyBzb2x2ZSBhIGRpZmZlcmVudCBwcm9ibGVtKiouIFRoZSBtdWx0aWNsYXNzIGJvb3N0ZWQgZGVjaXNpb24gdHJlZSBpcyBtb3N0IHN1aXRhYmxlIGZvciBub25wYXJhbWV0cmljIHRhc2tzLCBlLmcuIHRhc2tzIGRlc2lnbmVkIHRvIGJ1aWxkIHJhbmtpbmdzLCBzbyBpdCBpcyBub3QgdXNlZnVsIGZvciB1cy4KCkFsc28sIG5vcm1hbGx5IGJlZm9yZSBlbWJhcmtpbmcgb24gbW9yZSBjb21wbGV4IG1hY2hpbmUgbGVhcm5pbmcgbW9kZWxzIGUuZyBlbnNlbWJsZSBtZXRob2RzLCBpdCdzIGEgZ29vZCBpZGVhIHRvIGJ1aWxkIHRoZSBzaW1wbGVzdCBwb3NzaWJsZSBtb2RlbCB0byBnZXQgYW4gaWRlYSBvZiB3aGF0IGlzIGdvaW5nIG9uLiBTbyBmb3IgdGhpcyBsZXNzb24sIHdlJ2xsIHN0YXJ0IHdpdGggYSBgbXVsdGlub21pYWwgbG9naXN0aWMgcmVncmVzc2lvbmAgbW9kZWwuCgo+IExvZ2lzdGljIHJlZ3Jlc3Npb24gaXMgYSB0ZWNobmlxdWUgdXNlZCB3aGVuIHRoZSBvdXRjb21lIHZhcmlhYmxlIGlzIGNhdGVnb3JpY2FsIChvciBub21pbmFsKS4gRm9yIEJpbmFyeSBsb2dpc3RpYyByZWdyZXNzaW9uIHRoZSBudW1iZXIgb2Ygb3V0Y29tZSB2YXJpYWJsZXMgaXMgdHdvLCB3aGVyZWFzIHRoZSBudW1iZXIgb2Ygb3V0Y29tZSB2YXJpYWJsZXMgZm9yIG11bHRpbm9taWFsIGxvZ2lzdGljIHJlZ3Jlc3Npb24gaXMgbW9yZSB0aGFuIHR3by4gU2VlIFtBZHZhbmNlZCBSZWdyZXNzaW9uIE1ldGhvZHNdKGh0dHBzOi8vYm9va2Rvd24ub3JnL2NodWEvYmVyNjQyX2FkdmFuY2VkX3JlZ3Jlc3Npb24vbXVsdGlub21pYWwtbG9naXN0aWMtcmVncmVzc2lvbi5odG1sKSBmb3IgZnVydGhlciByZWFkaW5nLgoKIyMgNC4gVHJhaW4gYW5kIGV2YWx1YXRlIGEgTXVsdGlub21pYWwgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbC4KCkluIFRpZHltb2RlbHMsIGBwYXJzbmlwOjptdWx0aW5vbV9yZWcoKWAsIGRlZmluZXMgYSBtb2RlbCB0aGF0IHVzZXMgbGluZWFyIHByZWRpY3RvcnMgdG8gcHJlZGljdCBtdWx0aWNsYXNzIGRhdGEgdXNpbmcgdGhlIG11bHRpbm9taWFsIGRpc3RyaWJ1dGlvbi4gU2VlIGA/bXVsdGlub21fcmVnKClgIGZvciB0aGUgZGlmZmVyZW50IHdheXMvZW5naW5lcyB5b3UgY2FuIHVzZSB0byBmaXQgdGhpcyBtb2RlbC4KCkZvciB0aGlzIGV4YW1wbGUsIHdlJ2xsIGZpdCBhIE11bHRpbm9taWFsIHJlZ3Jlc3Npb24gbW9kZWwgdmlhIHRoZSBkZWZhdWx0IFtubmV0XShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvbm5ldC9ubmV0LnBkZikgZW5naW5lLgoKPiBJIHBpY2tlZCBhIHZhbHVlIGZvciBgcGVuYWx0eWAgc29ydCBvZiByYW5kb21seS4gVGhlcmUgYXJlIGJldHRlciB3YXlzIHRvIGNob29zZSB0aGlzIHZhbHVlIHRoYXQgaXMsIGJ5IHVzaW5nIGByZXNhbXBsaW5nYCBhbmQgYHR1bmluZ2AgdGhlIG1vZGVsIHdoaWNoIHdlJ2xsIGRpc2N1c3MgbGF0ZXIuCj4KPiBTZWUgW1RpZHltb2RlbHM6IEdldCBTdGFydGVkXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy9zdGFydC90dW5pbmcvKSBpbiBjYXNlIHlvdSB3YW50IHRvIGxlYXJuIG1vcmUgb24gaG93IHRvIHR1bmUgbW9kZWwgaHlwZXJwYXJhbWV0ZXJzLgoKYGBge3IgbXVsdGlub3JtX3JlZ30KIyBDcmVhdGUgYSBtdWx0aW5vbWlhbCByZWdyZXNzaW9uIG1vZGVsIHNwZWNpZmljYXRpb24KbXJfc3BlYyA8LSBtdWx0aW5vbV9yZWcocGVuYWx0eSA9IDEpICU+JSAKICBzZXRfZW5naW5lKCJubmV0IiwgTWF4Tld0cyA9IDIwODYpICU+JSAKICBzZXRfbW9kZSgiY2xhc3NpZmljYXRpb24iKQoKIyBQcmludCBtb2RlbCBzcGVjaWZpY2F0aW9uCm1yX3NwZWMKCmBgYAoKR3JlYXQgam9iIPCfpbMhIE5vdyB0aGF0IHdlIGhhdmUgYSByZWNpcGUgYW5kIGEgbW9kZWwgc3BlY2lmaWNhdGlvbiwgd2UgbmVlZCB0byBmaW5kIGEgd2F5IG9mIGJ1bmRsaW5nIHRoZW0gdG9nZXRoZXIgaW50byBhbiBvYmplY3QgdGhhdCB3aWxsIGZpcnN0IHByZXByb2Nlc3MgdGhlIGRhdGEgdGhlbiBmaXQgdGhlIG1vZGVsIG9uIHRoZSBwcmVwcm9jZXNzZWQgZGF0YSBhbmQgYWxzbyBhbGxvdyBmb3IgcG90ZW50aWFsIHBvc3QtcHJvY2Vzc2luZyBhY3Rpdml0aWVzLiBJbiBUaWR5bW9kZWxzLCB0aGlzIGNvbnZlbmllbnQgb2JqZWN0IGlzIGNhbGxlZCBhIFtgd29ya2Zsb3dgXShodHRwczovL3dvcmtmbG93cy50aWR5bW9kZWxzLm9yZy8pIGFuZCBjb252ZW5pZW50bHkgaG9sZHMgeW91ciBtb2RlbGluZyBjb21wb25lbnRzISBUaGlzIGlzIHdoYXQgd2UnZCBjYWxsICpwaXBlbGluZXMqIGluICpQeXRob24qLgoKU28gbGV0J3MgYnVuZGxlIGV2ZXJ5dGhpbmcgdXAgaW50byBhIHdvcmtmbG93IfCfk6YKCmBgYHtyIHdvcmtmbG93fQojIEJ1bmRsZSByZWNpcGUgYW5kIG1vZGVsIHNwZWNpZmljYXRpb24KbXJfd2YgPC0gd29ya2Zsb3coKSAlPiUgCiAgYWRkX3JlY2lwZShjdWlzaW5lc19yZWNpcGUpICU+JSAKICBhZGRfbW9kZWwobXJfc3BlYykKCiMgUHJpbnQgb3V0IHdvcmtmbG93Cm1yX3dmCgpgYGAKCldvcmtmbG93cyDwn5GM8J+RjCEgQSAqKmB3b3JrZmxvdygpYCoqIGNhbiBiZSBmaXQgaW4gbXVjaCB0aGUgc2FtZSB3YXkgYSBtb2RlbCBjYW4uIFNvLCB0aW1lIHRvIHRyYWluIGEgbW9kZWwhCgpgYGB7ciB0cmFpbn0KIyBUcmFpbiBhIG11bHRpbm9taWFsIHJlZ3Jlc3Npb24gbW9kZWwKbXJfZml0IDwtIGZpdChvYmplY3QgPSBtcl93ZiwgZGF0YSA9IGN1aXNpbmVzX3RyYWluKQoKbXJfZml0CmBgYAoKVGhlIG91dHB1dCBzaG93cyB0aGUgY29lZmZpY2llbnRzIHRoYXQgdGhlIG1vZGVsIGxlYXJuZWQgZHVyaW5nIHRyYWluaW5nLgoKIyMjIEV2YWx1YXRlIHRoZSBUcmFpbmVkIE1vZGVsCgpJdCdzIHRpbWUgdG8gc2VlIGhvdyB0aGUgbW9kZWwgcGVyZm9ybWVkIPCfk48gYnkgZXZhbHVhdGluZyBpdCBvbiBhIHRlc3Qgc2V0ISBMZXQncyBiZWdpbiBieSBtYWtpbmcgcHJlZGljdGlvbnMgb24gdGhlIHRlc3Qgc2V0LgoKYGBge3IgdGVzdH0KIyBNYWtlIHByZWRpY3Rpb25zIG9uIHRoZSB0ZXN0IHNldApyZXN1bHRzIDwtIGN1aXNpbmVzX3Rlc3QgJT4lIHNlbGVjdChjdWlzaW5lKSAlPiUgCiAgYmluZF9jb2xzKG1yX2ZpdCAlPiUgcHJlZGljdChuZXdfZGF0YSA9IGN1aXNpbmVzX3Rlc3QpKQoKIyBQcmludCBvdXQgcmVzdWx0cwpyZXN1bHRzICU+JSAKICBzbGljZV9oZWFkKG4gPSA1KQoKYGBgCgpHcmVhdCBqb2IhIEluIFRpZHltb2RlbHMsIGV2YWx1YXRpbmcgbW9kZWwgcGVyZm9ybWFuY2UgY2FuIGJlIGRvbmUgdXNpbmcgW3lhcmRzdGlja10oaHR0cHM6Ly95YXJkc3RpY2sudGlkeW1vZGVscy5vcmcvKSAtIGEgcGFja2FnZSB1c2VkIHRvIG1lYXN1cmUgdGhlIGVmZmVjdGl2ZW5lc3Mgb2YgbW9kZWxzIHVzaW5nIHBlcmZvcm1hbmNlIG1ldHJpY3MuIEFzIHdlIGRpZCBpbiBvdXIgbG9naXN0aWMgcmVncmVzc2lvbiBsZXNzb24sIGxldCdzIGJlZ2luIGJ5IGNvbXB1dGluZyBhIGNvbmZ1c2lvbiBtYXRyaXguCgpgYGB7ciBjb25mX21hdH0KIyBDb25mdXNpb24gbWF0cml4IGZvciBjYXRlZ29yaWNhbCBkYXRhCmNvbmZfbWF0KGRhdGEgPSByZXN1bHRzLCB0cnV0aCA9IGN1aXNpbmUsIGVzdGltYXRlID0gLnByZWRfY2xhc3MpCgoKYGBgCgpXaGVuIGRlYWxpbmcgd2l0aCBtdWx0aXBsZSBjbGFzc2VzLCBpdCdzIGdlbmVyYWxseSBtb3JlIGludHVpdGl2ZSB0byB2aXN1YWxpemUgdGhpcyBhcyBhIGhlYXQgbWFwLCBsaWtlIHRoaXM6CgpgYGB7ciBjb25mX3Zpen0KdXBkYXRlX2dlb21fZGVmYXVsdHMoZ2VvbSA9ICJ0aWxlIiwgbmV3ID0gbGlzdChjb2xvciA9ICJibGFjayIsIGFscGhhID0gMC43KSkKIyBWaXN1YWxpemUgY29uZnVzaW9uIG1hdHJpeApyZXN1bHRzICU+JSAKICBjb25mX21hdChjdWlzaW5lLCAucHJlZF9jbGFzcykgJT4lIAogIGF1dG9wbG90KHR5cGUgPSAiaGVhdG1hcCIpCmBgYAoKVGhlIGRhcmtlciBzcXVhcmVzIGluIHRoZSBjb25mdXNpb24gbWF0cml4IHBsb3QgaW5kaWNhdGUgaGlnaCBudW1iZXJzIG9mIGNhc2VzLCBhbmQgeW91IGNhbiBob3BlZnVsbHkgc2VlIGEgZGlhZ29uYWwgbGluZSBvZiBkYXJrZXIgc3F1YXJlcyBpbmRpY2F0aW5nIGNhc2VzIHdoZXJlIHRoZSBwcmVkaWN0ZWQgYW5kIGFjdHVhbCBsYWJlbCBhcmUgdGhlIHNhbWUuCgpMZXQncyBub3cgY2FsY3VsYXRlIHN1bW1hcnkgc3RhdGlzdGljcyBmb3IgdGhlIGNvbmZ1c2lvbiBtYXRyaXguCgpgYGB7ciBjb25mX3N0YXRzfQojIFN1bW1hcnkgc3RhdHMgZm9yIGNvbmZ1c2lvbiBtYXRyaXgKY29uZl9tYXQoZGF0YSA9IHJlc3VsdHMsIHRydXRoID0gY3Vpc2luZSwgZXN0aW1hdGUgPSAucHJlZF9jbGFzcykgJT4lIHN1bW1hcnkoKQpgYGAKCklmIHdlIG5hcnJvdyBkb3duIHRvIHNvbWUgbWV0cmljcyBzdWNoIGFzIGFjY3VyYWN5LCBzZW5zaXRpdml0eSwgcHB2LCB3ZSBhcmUgbm90IGJhZGx5IG9mZiBmb3IgYSBzdGFydCDwn6WzIQoKIyMgNC4gRGlnZ2luZyBEZWVwZXIKCkxldCdzIGFzayBvbmUgc3VidGxlIHF1ZXN0aW9uOiBXaGF0IGNyaXRlcmlhIGlzIHVzZWQgdG8gc2V0dGxlIGZvciBhIGdpdmVuIHR5cGUgb2YgY3Vpc2luZSBhcyB0aGUgcHJlZGljdGVkIG91dGNvbWU/CgpXZWxsLCBTdGF0aXN0aWNhbCBtYWNoaW5lIGxlYXJuaW5nIGFsZ29yaXRobXMsIGxpa2UgbG9naXN0aWMgcmVncmVzc2lvbiwgYXJlIGJhc2VkIG9uIGBwcm9iYWJpbGl0eWA7IHNvIHdoYXQgYWN0dWFsbHkgZ2V0cyBwcmVkaWN0ZWQgYnkgYSBjbGFzc2lmaWVyIGlzIGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG92ZXIgYSBzZXQgb2YgcG9zc2libGUgb3V0Y29tZXMuIFRoZSBjbGFzcyB3aXRoIHRoZSBoaWdoZXN0IHByb2JhYmlsaXR5IGlzIHRoZW4gY2hvc2VuIGFzIHRoZSBtb3N0IGxpa2VseSBvdXRjb21lIGZvciB0aGUgZ2l2ZW4gb2JzZXJ2YXRpb25zLgoKTGV0J3Mgc2VlIHRoaXMgaW4gYWN0aW9uIGJ5IG1ha2luZyBib3RoIGhhcmQgY2xhc3MgcHJlZGljdGlvbnMgYW5kIHByb2JhYmlsaXRpZXMuCgpgYGB7ciBwcmVkX3Byb2J9CiMgTWFrZSBoYXJkIGNsYXNzIHByZWRpY3Rpb24gYW5kIHByb2JhYmlsaXRpZXMKcmVzdWx0c19wcm9iIDwtIGN1aXNpbmVzX3Rlc3QgJT4lCiAgc2VsZWN0KGN1aXNpbmUpICU+JSAKICBiaW5kX2NvbHMobXJfZml0ICU+JSBwcmVkaWN0KG5ld19kYXRhID0gY3Vpc2luZXNfdGVzdCkpICU+JSAKICBiaW5kX2NvbHMobXJfZml0ICU+JSBwcmVkaWN0KG5ld19kYXRhID0gY3Vpc2luZXNfdGVzdCwgdHlwZSA9ICJwcm9iIikpCgojIFByaW50IG91dCByZXN1bHRzCnJlc3VsdHNfcHJvYiAlPiUgCiAgc2xpY2VfaGVhZChuID0gNSkKICAKCmBgYAoKTXVjaCBiZXR0ZXIhCgrinIUgQ2FuIHlvdSBleHBsYWluIHdoeSB0aGUgbW9kZWwgaXMgcHJldHR5IHN1cmUgdGhhdCB0aGUgZmlyc3Qgb2JzZXJ2YXRpb24gaXMgVGhhaT8KCiMjICoq8J+agENoYWxsZW5nZSoqCgpJbiB0aGlzIGxlc3NvbiwgeW91IHVzZWQgeW91ciBjbGVhbmVkIGRhdGEgdG8gYnVpbGQgYSBtYWNoaW5lIGxlYXJuaW5nIG1vZGVsIHRoYXQgY2FuIHByZWRpY3QgYSBuYXRpb25hbCBjdWlzaW5lIGJhc2VkIG9uIGEgc2VyaWVzIG9mIGluZ3JlZGllbnRzLiBUYWtlIHNvbWUgdGltZSB0byByZWFkIHRocm91Z2ggdGhlIFttYW55IG9wdGlvbnNdKGh0dHBzOi8vd3d3LnRpZHltb2RlbHMub3JnL2ZpbmQvcGFyc25pcC8jbW9kZWxzKSBUaWR5bW9kZWxzIHByb3ZpZGVzIHRvIGNsYXNzaWZ5IGRhdGEgYW5kIFtvdGhlciB3YXlzXShodHRwczovL3BhcnNuaXAudGlkeW1vZGVscy5vcmcvYXJ0aWNsZXMvYXJ0aWNsZXMvRXhhbXBsZXMuaHRtbCNtdWx0aW5vbV9yZWctbW9kZWxzKSB0byBmaXQgbXVsdGlub21pYWwgcmVncmVzc2lvbi4KCiMjIyMgVEhBTksgWU9VIFRPOgoKW2BBbGxpc29uIEhvcnN0YF0oaHR0cHM6Ly90d2l0dGVyLmNvbS9hbGxpc29uX2hvcnN0LykgZm9yIGNyZWF0aW5nIHRoZSBhbWF6aW5nIGlsbHVzdHJhdGlvbnMgdGhhdCBtYWtlIFIgbW9yZSB3ZWxjb21pbmcgYW5kIGVuZ2FnaW5nLiBGaW5kIG1vcmUgaWxsdXN0cmF0aW9ucyBhdCBoZXIgW2dhbGxlcnldKGh0dHBzOi8vd3d3Lmdvb2dsZS5jb20vdXJsP3E9aHR0cHM6Ly9naXRodWIuY29tL2FsbGlzb25ob3JzdC9zdGF0cy1pbGx1c3RyYXRpb25zJnNhPUQmc291cmNlPWVkaXRvcnMmdXN0PTE2MjYzODA3NzI1MzAwMDAmdXNnPUFPdlZhdzN6Y2Z5Q2l6RlFacGtTTHp4aWlRRU0pLgoKW0Nhc3NpZSBCcmV2aXVdKGh0dHBzOi8vd3d3LnR3aXR0ZXIuY29tL2Nhc3NpZXZpZXcpIGFuZCBbSmVuIExvb3Blcl0oaHR0cHM6Ly93d3cudHdpdHRlci5jb20vamVubG9vcGVyKSBmb3IgY3JlYXRpbmcgdGhlIG9yaWdpbmFsIFB5dGhvbiB2ZXJzaW9uIG9mIHRoaXMgbW9kdWxlIOKZpe+4jwoKSGFwcHkgTGVhcm5pbmcsCgpbRXJpY10oaHR0cHM6Ly90d2l0dGVyLmNvbS9lcmljbnRheSksIEdvbGQgTWljcm9zb2Z0IExlYXJuIFN0dWRlbnQgQW1iYXNzYWRvci4K