Diagnosing Breast Cancer

using k-nn algorithm

Routine breast cancer screening allows the disease to be diagnosed and treated prior to it causing noticeable symptoms. The process of early detection involves examining the breast tissue for abnormal lumps or masses. If a lump is found, a fine-needle aspiration biopsy is performed, which uses a hollow needle to extract a small sample of cells from the mass. A clinician then examines the cells under a microscope to determine whether the mass is likely to be malignant or benign.

If machine learning could automate the identification of cancerous cells, it would provide considerable benefit to the health system. Automated processes are likely to improve the efficiency of the detection process, allowing physicians to spend less time diagnosing and more time treating the disease. An automated screening system might also provide greater detection accuracy by removing the inherently subjective human component from the process.

We will investigate the utility of machine learning for detecting cancer by applying the k-NN algorithm to measurements of biopsied cells from women with abnormal breast masses.

Data Collection

We will utilize the Wisconsin Breast Cancer Diagnostic dataset from the UCI Machine Learning Repository at http://archive.ics.uci.edu/ml. This data was donated by researchers of the University of Wisconsin and includes the measurements from digitized images of fine-needle aspirate of a breast mass. The values represent the characteristics of the cell nuclei present in the digital image.

The breast cancer data includes 569 examples of cancer biopsies, each with 32 features. One feature is an identification number, another is the cancer diagnosis, and 30 are numeric-valued laboratory measurements. The diagnosis is coded as “M” to indicate malignant or “B” to indicate benign.

Based on these names, all the features seem to relate to the shape and size of the cell nuclei. Unless you are an oncologist, you are unlikely to know how each relates to benign or malignant masses. These patterns will be revealed as we continue in the machine learning process.

exploring and preparing the data

Let’s explore the data and see whether we can shine some light on the relationships. In doing so, we will prepare the data for use with the k-NN learning method.

We’ll begin by importing the CSV data file, as we have done in previous chapters, saving the Wisconsin breast cancer data to the wbcd data frame:

wbcd <- read.csv("wisc_bc_data.csv", stringsAsFactors = FALSE)

Using the str(wbcd) command, we can confirm that the data is structured with 569 examples and 32 features as we expected. The first several lines of output are as follows:

str(wbcd)
'data.frame':   569 obs. of  32 variables:
 $ id                     : int  842302 842517 84300903 84348301 84358402 843786 844359 84458202 844981 84501001 ...
 $ diagnosis              : chr  "M" "M" "M" "M" ...
 $ radius_mean            : num  18 20.6 19.7 11.4 20.3 ...
 $ texture_mean           : num  10.4 17.8 21.2 20.4 14.3 ...
 $ perimeter_mean         : num  122.8 132.9 130 77.6 135.1 ...
 $ area_mean              : num  1001 1326 1203 386 1297 ...
 $ smoothness_mean        : num  0.1184 0.0847 0.1096 0.1425 0.1003 ...
 $ compactness_mean       : num  0.2776 0.0786 0.1599 0.2839 0.1328 ...
 $ concavity_mean         : num  0.3001 0.0869 0.1974 0.2414 0.198 ...
 $ concave.points_mean    : num  0.1471 0.0702 0.1279 0.1052 0.1043 ...
 $ symmetry_mean          : num  0.242 0.181 0.207 0.26 0.181 ...
 $ fractal_dimension_mean : num  0.0787 0.0567 0.06 0.0974 0.0588 ...
 $ radius_se              : num  1.095 0.543 0.746 0.496 0.757 ...
 $ texture_se             : num  0.905 0.734 0.787 1.156 0.781 ...
 $ perimeter_se           : num  8.59 3.4 4.58 3.44 5.44 ...
 $ area_se                : num  153.4 74.1 94 27.2 94.4 ...
 $ smoothness_se          : num  0.0064 0.00522 0.00615 0.00911 0.01149 ...
 $ compactness_se         : num  0.049 0.0131 0.0401 0.0746 0.0246 ...
 $ concavity_se           : num  0.0537 0.0186 0.0383 0.0566 0.0569 ...
 $ concave.points_se      : num  0.0159 0.0134 0.0206 0.0187 0.0188 ...
 $ symmetry_se            : num  0.03 0.0139 0.0225 0.0596 0.0176 ...
 $ fractal_dimension_se   : num  0.00619 0.00353 0.00457 0.00921 0.00511 ...
 $ radius_worst           : num  25.4 25 23.6 14.9 22.5 ...
 $ texture_worst          : num  17.3 23.4 25.5 26.5 16.7 ...
 $ perimeter_worst        : num  184.6 158.8 152.5 98.9 152.2 ...
 $ area_worst             : num  2019 1956 1709 568 1575 ...
 $ smoothness_worst       : num  0.162 0.124 0.144 0.21 0.137 ...
 $ compactness_worst      : num  0.666 0.187 0.424 0.866 0.205 ...
 $ concavity_worst        : num  0.712 0.242 0.45 0.687 0.4 ...
 $ concave.points_worst   : num  0.265 0.186 0.243 0.258 0.163 ...
 $ symmetry_worst         : num  0.46 0.275 0.361 0.664 0.236 ...
 $ fractal_dimension_worst: num  0.1189 0.089 0.0876 0.173 0.0768 ...

The first variable is an integer variable named id. As this is simply a unique identifier (ID) for each patient in the data, it does not provide useful information, and we will need to exclude it from the model.

Let’s drop the id feature altogether. As it is located in the first column, we can exclude it by making a copy of the wbcd data frame without column 1:

wbcd <- wbcd[-1]

The next variable, diagnosis, is of particular interest as it is the outcome we hope to predict. This feature indicates whether the example is from a benign or malignant mass. The table() output indicates that 357 masses are benign while 212 are malignant:

table(wbcd$diagnosis)

  B   M 
357 212 

Many R machine learning classifiers require that the target feature is coded as a factor, so we will need to recode the diagnosis variable. We will also take this opportunity to give the “B” and “M” values more informative labels using the labels parameter:

wbcd$diagnosis<- factor(wbcd$diagnosis, levels = c("B", "M"),
labels = c("Benign", "Malignant"))

Now, when we look at the prop.table() output, we notice that the values have been labeled Benign and Malignant with 62.7 percent and 37.3 percent of the masses, respectively:

round(prop.table(table(wbcd$diagnosis)) * 100, digits = 1)

   Benign Malignant 
     62.7      37.3 

The remaining 30 features are all numeric, and as expected, they consist of three different measurements of ten characteristics. For illustrative purposes, we will only take a closer look at three of these features:

summary(wbcd[c("radius_mean", "area_mean", "smoothness_mean")])
  radius_mean       area_mean      smoothness_mean  
 Min.   : 6.981   Min.   : 143.5   Min.   :0.05263  
 1st Qu.:11.700   1st Qu.: 420.3   1st Qu.:0.08637  
 Median :13.370   Median : 551.1   Median :0.09587  
 Mean   :14.127   Mean   : 654.9   Mean   :0.09636  
 3rd Qu.:15.780   3rd Qu.: 782.7   3rd Qu.:0.10530  
 Max.   :28.110   Max.   :2501.0   Max.   :0.16340  

Looking at the features side-by-side, do you notice anything problematic about the values? Recall that the distance calculation for k-NN is heavily dependent upon the measurement scale of the input features. Since smoothness ranges from 0.05 to 0.16 and area ranges from 143.5 to 2501.0, the impact of area is going to be much larger than the smoothness in the distance calculation. This could potentially cause problems for our classifier, so let’s apply normalization to rescale the features to a standard range of values.

Transformation - normalizing numeric data

To normalize these features, we need to create a normalize() function in R. This function takes a vector x of numeric values, and for each value in x, subtracts the minimum value in x and divides by the range of values in x. Finally, the resulting vector is returned. The code for this function is as follows:

normalize <- function(x) {
  return ((x - min(x)) / (max(x) - min(x)))
}

After executing the preceding code, the normalize() function is available for use in R. Let’s test the function on a couple of vectors:

normalize(c(1, 2, 3, 4, 5))
[1] 0.00 0.25 0.50 0.75 1.00
normalize(c(10, 20, 30, 40, 50))
[1] 0.00 0.25 0.50 0.75 1.00

The function appears to be working correctly. Despite the fact that the values in the second vector are 10 times larger than the first vector, after normalization, they both appear exactly the same.

We can now apply the normalize() function to the numeric features in our data frame. Rather than normalizing each of the 30 numeric variables individually, we will use one of R’s functions to automate the process.

The lapply() function takes a list and applies a specified function to each list element. As a data frame is a list of equal-length vectors, we can use lapply() to apply normalize() to each feature in the data frame. The final step is to convert the list returned by lapply() to a data frame, using the as.data.frame() function. The full process looks like this:

wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))

In plain English, this command applies the normalize() function to columns 2 through 31 in the wbcd data frame, converts the resulting list to a data frame, and assigns it the name wbcd_n. The _n suffix is used here as a reminder that the values in wbcd have been normalized.

To confirm that the transformation was applied correctly, let’s look at one variable’s summary statistics:

summary(wbcd_n$area_mean)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.0000  0.1174  0.1729  0.2169  0.2711  1.0000 

As expected, the area_mean variable, which originally ranged from 143.5 to 2501.0, now ranges from 0 to 1.

Data preparation - creating training and test datasets

Although all the 569 biopsies are labeled with a benign or malignant status, it is not very interesting to predict what we already know. Additionally, any performance measures we obtain during the training may be misleading as we do not know the extent to which cases have been overfitted or how well the learner will generalize to unseen cases. A more interesting question is how well our learner performs on a dataset of unlabeled data. If we had access to a laboratory, we could apply our learner to the measurements taken from the next 100 masses of unknown cancer status, and see how well the machine learner’s predictions compare to the diagnoses obtained using conventional methods.

In the absence of such data, we can simulate this scenario by dividing our data into two portions: a training dataset that will be used to build the k-NN model and a test dataset that will be used to estimate the predictive accuracy of the model. We will use the first 469 records for the training dataset and the remaining 100 to simulate new patients.

Using the data extraction methods given in Chapter 2, Managing and Understanding Data, we will split the wbcd_n data frame into wbcd_train and wbcd_test:

wbcd_train <- wbcd_n[1:469, ]
wbcd_test <- wbcd_n[470:569, ]

If the preceding commands are confusing, remember that data is extracted from data frames using the [row, column] syntax. A blank value for the row or column value indicates that all the rows or columns should be included. Hence, the first line of code takes rows 1 to 469 and all columns, and the second line takes 100 rows from 470 to 569 and all columns.

When we constructed our normalized training and test datasets, we excluded the target variable, diagnosis. For training the k-NN model, we will need to store these class labels in factor vectors, split between the training and test datasets:

wbcd_train_labels <- wbcd[1:469, 1]
wbcd_test_labels <- wbcd[470:569, 1]

This code takes the diagnosis factor in the first column of the wbcd data frame, and creates the vectors wbcd_train_labels and wbcd_test_labels. We will use these in the next steps of training and evaluating our classifier.

training a model on the data

Equipped with our training data and labels vector, we are now ready to classify our unknown records. For the k-NN algorithm, the training phase actually involves no model building; the process of training a lazy learner like k-NN simply involves storing the input data in a structured format.

To classify our test instances, we will use a k-NN implementation from the class package, which provides a set of basic R functions for classification. If this package is not already installed on your system, you can install it by typing:

install.packages("class")
Installing package into <U+393C><U+3E31>C:/Users/KEVIN/Documents/R/win-library/3.3<U+393C><U+3E32>
(as <U+393C><U+3E31>lib<U+393C><U+3E32> is unspecified)
trying URL 'https://cran.rstudio.com/bin/windows/contrib/3.3/class_7.3-14.zip'
Content type 'application/zip' length 101164 bytes (98 KB)
downloaded 98 KB
package ‘class’ successfully unpacked and MD5 sums checked

The downloaded binary packages are in
    C:\Users\KEVIN\AppData\Local\Temp\RtmpC6mVbm\downloaded_packages

To load the package during any session in which you wish to use the functions, simply enter the library(class) command.

library(class)

The knn() function in the class package provides a standard, classic implementation of the k-NN algorithm. For each instance in the test data, the function will identify the k-Nearest Neighbors, using Euclidean distance, where k is a user-specified number. The test instance is classified by taking a “vote” among the k-Nearest Neighbors-specifically, this involves assigning the class of the majority of the k neighbors. A tie vote is broken at random.

We now have nearly everything that we need to apply the k-NN algorithm to this data. We’ve split our data into training and test datasets, each with exactly the same numeric features. The labels for the training data are stored in a separate factor vector. The only remaining parameter is k, which specifies the number of neighbors to include in the vote.

As our training data includes 469 instances, we might try k = 21, an odd number roughly equal to the square root of 469. With a two-category outcome, using an odd number eliminates the chance of ending with a tie vote.

Now we can use the knn() function to classify the test data:

wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test, cl = wbcd_train_labels, k = 21)

The knn() function returns a factor vector of predicted labels for each of the examples in the test dataset, which we have assigned to wbcd_test_pred.

evaluating model performance

The next step of the process is to evaluate how well the predicted classes in the wbcd_ test_pred vector match up with the known values in the wbcd_test_labels vector. To do this, we can use the CrossTable() function in the gmodels package, which was introduced in Chapter 2, Managing and Understanding Data. If you haven’t done so already, please install this package, using the install.packages(“gmodels”) command.

After loading the package with the library(gmodels) command, we can create a cross tabulation indicating the agreement between the two vectors. Specifying prop.chisq = FALSE will remove the unnecessary chi-square values from the output:

CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, prop.chisq=FALSE)
Error: could not find function "CrossTable"

The cell percentages in the table indicate the proportion of values that fall into four categories. The top-left cell indicates the true negative results. These 61 of 100 values are cases where the mass was benign and the k-NN algorithm correctly identified it as such. The bottom-right cell indicates the true positive results, where the classifier and the clinically determined label agree that the mass is malignant. A total of 37 of 100 predictions were true positives.

The cells falling on the other diagonal contain counts of examples where the k-NN approach disagreed with the true label. The two examples in the lower-left cell are false negative results; in this case, the predicted value was benign, but the tumor was actually malignant. Errors in this direction could be extremely costly as they might lead a patient to believe that she is cancer-free, but in reality, the disease may continue to spread. The top-right cell would contain the false positive results, if there were any. These values occur when the model classifies a mass as malignant, but in reality, it was benign. Although such errors are less dangerous than a false negative result, they should also be avoided as they could lead to additional financial burden on the health care system or additional stress for the patient as additional tests or treatment may have to be provided. This is an R Markdown Notebook. When you execute code within the notebook, the results appear beneath the code.

A total of 2 out of 100, or 2 percent of masses were incorrectly classified by the k-NN approach. While 98 percent accuracy seems impressive for a few lines of R code, we might try another iteration of the model to see whether we can improve the performance and reduce the number of values that have been incorrectly classified, particularly because the errors were dangerous false negatives.

improving model performance

We will attempt two simple variations on our previous classifier. First, we will employ an alternative method for rescaling our numeric features. Second, we will try several different values for k.

Transformation - z-score standardization

Although normalization is traditionally used for k-NN classification, it may not always be the most appropriate way to rescale features. Since the z-score standardized values have no predefined minimum and maximum, extreme values are not compressed towards the center. One might suspect that with a malignant tumor, we might see some very extreme outliers as the tumors grow uncontrollably. It might, therefore, be reasonable to allow the outliers to be weighted more heavily in the distance calculation. Let’s see whether z-score standardization can improve our predictive accuracy.

To standardize a vector, we can use the R’s built-in scale() function, which, by default, rescales values using the z-score standardization. The scale() function offers the additional benefit that it can be applied directly to a data frame, so we can avoid the use of the lapply() function. To create a z-score standardized version of the wbcd data, we can use the following command:

This command rescales all the features, with the exception of diagnosis and stores the result as the wbcd_z data frame. The _z suffix is a reminder that the values were z-score transformed.

To confirm that the transformation was applied correctly, we can look at the summary statistics:

The mean of a z-score standardized variable should always be zero, and the range should be fairly compact. A z-score greater than 3 or less than -3 indicates an extremely rare value. With this in mind, the transformation seems to have worked.

As we had done earlier, we need to divide the data into training and test sets, and then classify the test instances using the knn() function. We’ll then compare the predicted labels to the actual labels using CrossTable():

Unfortunately, in the following table, the results of our new transformation show a slight decline in accuracy. The instances where we had correctly classified 98 percent of examples previously, we classified only 95 percent correctly this time. Making matters worse, we did no better at classifying the dangerous false negatives:

Testing alternative values of k

We may be able do even better by examining performance across various k values. Using the normalized training and test datasets, the same 100 records were classified using several different k values. The number of false negatives and false positives are shown for each iteration

Although the classifier was never perfect, the 1-NN approach was able to avoid some of the false negatives at the expense of adding false positives. It is important to keep in mind, however, that it would be unwise to tailor our approach too closely to our test data; after all, a different set of 100 patient records is likely to be somewhat different from those used to measure our performance.

EOF

LS0tDQp0aXRsZTogIkhXMDEgLSBrLW5uIGFsZ29yaXRobSAtIERpYWdub3NpbmcgQnJlYXN0IENhbmNlciINCmF1dGhvcjogIkhvYSBRdWFjaCINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCiMgRGlhZ25vc2luZyBCcmVhc3QgQ2FuY2VyDQojIyB1c2luZyBrLW5uIGFsZ29yaXRobQ0KDQpSb3V0aW5lIGJyZWFzdCBjYW5jZXIgc2NyZWVuaW5nIGFsbG93cyB0aGUgZGlzZWFzZSB0byBiZSBkaWFnbm9zZWQgYW5kIHRyZWF0ZWQgcHJpb3INCnRvIGl0IGNhdXNpbmcgbm90aWNlYWJsZSBzeW1wdG9tcy4gVGhlIHByb2Nlc3Mgb2YgZWFybHkgZGV0ZWN0aW9uIGludm9sdmVzIGV4YW1pbmluZw0KdGhlIGJyZWFzdCB0aXNzdWUgZm9yIGFibm9ybWFsIGx1bXBzIG9yIG1hc3Nlcy4gSWYgYSBsdW1wIGlzIGZvdW5kLCBhIGZpbmUtbmVlZGxlDQphc3BpcmF0aW9uIGJpb3BzeSBpcyBwZXJmb3JtZWQsIHdoaWNoIHVzZXMgYSBob2xsb3cgbmVlZGxlIHRvIGV4dHJhY3QgYSBzbWFsbCBzYW1wbGUNCm9mIGNlbGxzIGZyb20gdGhlIG1hc3MuIEEgY2xpbmljaWFuIHRoZW4gZXhhbWluZXMgdGhlIGNlbGxzIHVuZGVyIGEgbWljcm9zY29wZSB0bw0KZGV0ZXJtaW5lIHdoZXRoZXIgdGhlIG1hc3MgaXMgbGlrZWx5IHRvIGJlIG1hbGlnbmFudCBvciBiZW5pZ24uDQoNCklmIG1hY2hpbmUgbGVhcm5pbmcgY291bGQgYXV0b21hdGUgdGhlIGlkZW50aWZpY2F0aW9uIG9mIGNhbmNlcm91cyBjZWxscywgaXQgd291bGQNCnByb3ZpZGUgY29uc2lkZXJhYmxlIGJlbmVmaXQgdG8gdGhlIGhlYWx0aCBzeXN0ZW0uIEF1dG9tYXRlZCBwcm9jZXNzZXMgYXJlIGxpa2VseQ0KdG8gaW1wcm92ZSB0aGUgZWZmaWNpZW5jeSBvZiB0aGUgZGV0ZWN0aW9uIHByb2Nlc3MsIGFsbG93aW5nIHBoeXNpY2lhbnMgdG8gc3BlbmQgbGVzcw0KdGltZSBkaWFnbm9zaW5nIGFuZCBtb3JlIHRpbWUgdHJlYXRpbmcgdGhlIGRpc2Vhc2UuIEFuIGF1dG9tYXRlZCBzY3JlZW5pbmcgc3lzdGVtDQptaWdodCBhbHNvIHByb3ZpZGUgZ3JlYXRlciBkZXRlY3Rpb24gYWNjdXJhY3kgYnkgcmVtb3ZpbmcgdGhlIGluaGVyZW50bHkgc3ViamVjdGl2ZQ0KaHVtYW4gY29tcG9uZW50IGZyb20gdGhlIHByb2Nlc3MuDQoNCldlIHdpbGwgaW52ZXN0aWdhdGUgdGhlIHV0aWxpdHkgb2YgbWFjaGluZSBsZWFybmluZyBmb3IgZGV0ZWN0aW5nIGNhbmNlciBieSBhcHBseWluZw0KdGhlIGstTk4gYWxnb3JpdGhtIHRvIG1lYXN1cmVtZW50cyBvZiBiaW9wc2llZCBjZWxscyBmcm9tIHdvbWVuIHdpdGggYWJub3JtYWwNCmJyZWFzdCBtYXNzZXMuDQoNCiMjRGF0YSBDb2xsZWN0aW9uDQoNCldlIHdpbGwgdXRpbGl6ZSB0aGUgV2lzY29uc2luIEJyZWFzdCBDYW5jZXIgRGlhZ25vc3RpYyBkYXRhc2V0IGZyb20gdGhlIFVDSQ0KTWFjaGluZSBMZWFybmluZyBSZXBvc2l0b3J5IGF0IGh0dHA6Ly9hcmNoaXZlLmljcy51Y2kuZWR1L21sLiBUaGlzIGRhdGENCndhcyBkb25hdGVkIGJ5IHJlc2VhcmNoZXJzIG9mIHRoZSBVbml2ZXJzaXR5IG9mIFdpc2NvbnNpbiBhbmQgaW5jbHVkZXMgdGhlDQptZWFzdXJlbWVudHMgZnJvbSBkaWdpdGl6ZWQgaW1hZ2VzIG9mIGZpbmUtbmVlZGxlIGFzcGlyYXRlIG9mIGEgYnJlYXN0IG1hc3MuIFRoZQ0KdmFsdWVzIHJlcHJlc2VudCB0aGUgY2hhcmFjdGVyaXN0aWNzIG9mIHRoZSBjZWxsIG51Y2xlaSBwcmVzZW50IGluIHRoZSBkaWdpdGFsIGltYWdlLg0KDQpUaGUgYnJlYXN0IGNhbmNlciBkYXRhIGluY2x1ZGVzIDU2OSBleGFtcGxlcyBvZiBjYW5jZXIgYmlvcHNpZXMsIGVhY2ggd2l0aA0KMzIgZmVhdHVyZXMuIE9uZSBmZWF0dXJlIGlzIGFuIGlkZW50aWZpY2F0aW9uIG51bWJlciwgYW5vdGhlciBpcyB0aGUgY2FuY2VyIGRpYWdub3NpcywNCmFuZCAzMCBhcmUgbnVtZXJpYy12YWx1ZWQgbGFib3JhdG9yeSBtZWFzdXJlbWVudHMuIFRoZSBkaWFnbm9zaXMgaXMgY29kZWQgYXMNCiJNIiB0byBpbmRpY2F0ZSBtYWxpZ25hbnQgb3IgIkIiIHRvIGluZGljYXRlIGJlbmlnbi4NCg0KQmFzZWQgb24gdGhlc2UgbmFtZXMsIGFsbCB0aGUgZmVhdHVyZXMgc2VlbSB0byByZWxhdGUgdG8gdGhlIHNoYXBlIGFuZCBzaXplIG9mIHRoZSBjZWxsDQpudWNsZWkuIFVubGVzcyB5b3UgYXJlIGFuIG9uY29sb2dpc3QsIHlvdSBhcmUgdW5saWtlbHkgdG8ga25vdyBob3cgZWFjaCByZWxhdGVzIHRvDQpiZW5pZ24gb3IgbWFsaWduYW50IG1hc3Nlcy4gVGhlc2UgcGF0dGVybnMgd2lsbCBiZSByZXZlYWxlZCBhcyB3ZSBjb250aW51ZSBpbiB0aGUNCm1hY2hpbmUgbGVhcm5pbmcgcHJvY2Vzcy4NCg0KIyNleHBsb3JpbmcgYW5kIHByZXBhcmluZyB0aGUgZGF0YQ0KDQpMZXQncyBleHBsb3JlIHRoZSBkYXRhIGFuZCBzZWUgd2hldGhlciB3ZSBjYW4gc2hpbmUgc29tZSBsaWdodCBvbiB0aGUgcmVsYXRpb25zaGlwcy4NCkluIGRvaW5nIHNvLCB3ZSB3aWxsIHByZXBhcmUgdGhlIGRhdGEgZm9yIHVzZSB3aXRoIHRoZSBrLU5OIGxlYXJuaW5nIG1ldGhvZC4NCg0KV2UnbGwgYmVnaW4gYnkgaW1wb3J0aW5nIHRoZSBDU1YgZGF0YSBmaWxlLCBhcyB3ZSBoYXZlIGRvbmUgaW4gcHJldmlvdXMgY2hhcHRlcnMsDQpzYXZpbmcgdGhlIFdpc2NvbnNpbiBicmVhc3QgY2FuY2VyIGRhdGEgdG8gdGhlIHdiY2QgZGF0YSBmcmFtZToNCg0KYGBge3IgZXZhbD1UUlVFLCBlY2hvPUZBTFNFfQ0Kc2V0d2QoIkM6XFxVc2Vyc1xcS0VWSU5cXERvd25sb2Fkc1xcX0NTVSBFYXN0IEJheVxcUlxcTWFjaGluZS1MZWFybmluZy13aXRoLVItZGF0YXNldHMtbWFzdGVyIikNCmBgYA0KDQoNCmBgYHtyfQ0Kd2JjZCA8LSByZWFkLmNzdigid2lzY19iY19kYXRhLmNzdiIsIHN0cmluZ3NBc0ZhY3RvcnMgPSBGQUxTRSkNCmBgYA0KDQpVc2luZyB0aGUgc3RyKHdiY2QpIGNvbW1hbmQsIHdlIGNhbiBjb25maXJtIHRoYXQgdGhlIGRhdGEgaXMgc3RydWN0dXJlZCB3aXRoDQo1NjkgZXhhbXBsZXMgYW5kIDMyIGZlYXR1cmVzIGFzIHdlIGV4cGVjdGVkLiBUaGUgZmlyc3Qgc2V2ZXJhbCBsaW5lcyBvZiBvdXRwdXQNCmFyZSBhcyBmb2xsb3dzOg0KDQpgYGB7cn0NCnN0cih3YmNkKQ0KYGBgDQoNClRoZSBmaXJzdCB2YXJpYWJsZSBpcyBhbiBpbnRlZ2VyIHZhcmlhYmxlIG5hbWVkIGlkLiBBcyB0aGlzIGlzIHNpbXBseSBhIHVuaXF1ZQ0KaWRlbnRpZmllciAoSUQpIGZvciBlYWNoIHBhdGllbnQgaW4gdGhlIGRhdGEsIGl0IGRvZXMgbm90IHByb3ZpZGUgdXNlZnVsIGluZm9ybWF0aW9uLA0KYW5kIHdlIHdpbGwgbmVlZCB0byBleGNsdWRlIGl0IGZyb20gdGhlIG1vZGVsLg0KDQpMZXQncyBkcm9wIHRoZSBpZCBmZWF0dXJlIGFsdG9nZXRoZXIuIEFzIGl0IGlzIGxvY2F0ZWQgaW4gdGhlIGZpcnN0IGNvbHVtbiwgd2UgY2FuDQpleGNsdWRlIGl0IGJ5IG1ha2luZyBhIGNvcHkgb2YgdGhlIHdiY2QgZGF0YSBmcmFtZSB3aXRob3V0IGNvbHVtbiAxOg0KDQpgYGB7cn0NCndiY2QgPC0gd2JjZFstMV0NCmBgYA0KDQpUaGUgbmV4dCB2YXJpYWJsZSwgZGlhZ25vc2lzLCBpcyBvZiBwYXJ0aWN1bGFyIGludGVyZXN0IGFzIGl0IGlzIHRoZSBvdXRjb21lIHdlDQpob3BlIHRvIHByZWRpY3QuIFRoaXMgZmVhdHVyZSBpbmRpY2F0ZXMgd2hldGhlciB0aGUgZXhhbXBsZSBpcyBmcm9tIGEgYmVuaWduDQpvciBtYWxpZ25hbnQgbWFzcy4gVGhlIHRhYmxlKCkgb3V0cHV0IGluZGljYXRlcyB0aGF0IDM1NyBtYXNzZXMgYXJlIGJlbmlnbg0Kd2hpbGUgMjEyIGFyZSBtYWxpZ25hbnQ6DQoNCg0KYGBge3J9DQp0YWJsZSh3YmNkJGRpYWdub3NpcykNCmBgYA0KDQpNYW55IFIgbWFjaGluZSBsZWFybmluZyBjbGFzc2lmaWVycyByZXF1aXJlIHRoYXQgdGhlIHRhcmdldCBmZWF0dXJlIGlzIGNvZGVkIGFzIGENCmZhY3Rvciwgc28gd2Ugd2lsbCBuZWVkIHRvIHJlY29kZSB0aGUgZGlhZ25vc2lzIHZhcmlhYmxlLiBXZSB3aWxsIGFsc28gdGFrZSB0aGlzDQpvcHBvcnR1bml0eSB0byBnaXZlIHRoZSAiQiIgYW5kICJNIiB2YWx1ZXMgbW9yZSBpbmZvcm1hdGl2ZSBsYWJlbHMgdXNpbmcgdGhlDQpsYWJlbHMgcGFyYW1ldGVyOg0KDQpgYGB7cn0NCndiY2QkZGlhZ25vc2lzPC0gZmFjdG9yKHdiY2QkZGlhZ25vc2lzLCBsZXZlbHMgPSBjKCJCIiwgIk0iKSwNCmxhYmVscyA9IGMoIkJlbmlnbiIsICJNYWxpZ25hbnQiKSkNCmBgYA0KDQpOb3csIHdoZW4gd2UgbG9vayBhdCB0aGUgcHJvcC50YWJsZSgpIG91dHB1dCwgd2Ugbm90aWNlIHRoYXQgdGhlIHZhbHVlcyBoYXZlDQpiZWVuIGxhYmVsZWQgQmVuaWduIGFuZCBNYWxpZ25hbnQgd2l0aCA2Mi43IHBlcmNlbnQgYW5kIDM3LjMgcGVyY2VudCBvZiB0aGUNCm1hc3NlcywgcmVzcGVjdGl2ZWx5Og0KDQpgYGB7cn0NCnJvdW5kKHByb3AudGFibGUodGFibGUod2JjZCRkaWFnbm9zaXMpKSAqIDEwMCwgZGlnaXRzID0gMSkNCmBgYA0KDQoNClRoZSByZW1haW5pbmcgMzAgZmVhdHVyZXMgYXJlIGFsbCBudW1lcmljLCBhbmQgYXMgZXhwZWN0ZWQsIHRoZXkgY29uc2lzdCBvZiB0aHJlZQ0KZGlmZmVyZW50IG1lYXN1cmVtZW50cyBvZiB0ZW4gY2hhcmFjdGVyaXN0aWNzLiBGb3IgaWxsdXN0cmF0aXZlIHB1cnBvc2VzLCB3ZSB3aWxsDQpvbmx5IHRha2UgYSBjbG9zZXIgbG9vayBhdCB0aHJlZSBvZiB0aGVzZSBmZWF0dXJlczoNCg0KYGBge3J9DQpzdW1tYXJ5KHdiY2RbYygicmFkaXVzX21lYW4iLCAiYXJlYV9tZWFuIiwgInNtb290aG5lc3NfbWVhbiIpXSkNCmBgYA0KDQpMb29raW5nIGF0IHRoZSBmZWF0dXJlcyBzaWRlLWJ5LXNpZGUsIGRvIHlvdSBub3RpY2UgYW55dGhpbmcgcHJvYmxlbWF0aWMgYWJvdXQgdGhlDQp2YWx1ZXM/IFJlY2FsbCB0aGF0IHRoZSBkaXN0YW5jZSBjYWxjdWxhdGlvbiBmb3Igay1OTiBpcyBoZWF2aWx5IGRlcGVuZGVudCB1cG9uDQp0aGUgbWVhc3VyZW1lbnQgc2NhbGUgb2YgdGhlIGlucHV0IGZlYXR1cmVzLiBTaW5jZSBzbW9vdGhuZXNzIHJhbmdlcyBmcm9tIDAuMDUgdG8NCjAuMTYgYW5kIGFyZWEgcmFuZ2VzIGZyb20gMTQzLjUgdG8gMjUwMS4wLCB0aGUgaW1wYWN0IG9mIGFyZWEgaXMgZ29pbmcgdG8gYmUgbXVjaA0KbGFyZ2VyIHRoYW4gdGhlIHNtb290aG5lc3MgaW4gdGhlIGRpc3RhbmNlIGNhbGN1bGF0aW9uLiBUaGlzIGNvdWxkIHBvdGVudGlhbGx5IGNhdXNlDQpwcm9ibGVtcyBmb3Igb3VyIGNsYXNzaWZpZXIsIHNvIGxldCdzIGFwcGx5IG5vcm1hbGl6YXRpb24gdG8gcmVzY2FsZSB0aGUgZmVhdHVyZXMgdG8gYQ0Kc3RhbmRhcmQgcmFuZ2Ugb2YgdmFsdWVzLg0KDQojI1RyYW5zZm9ybWF0aW9uIC0gbm9ybWFsaXppbmcgbnVtZXJpYyBkYXRhDQoNClRvIG5vcm1hbGl6ZSB0aGVzZSBmZWF0dXJlcywgd2UgbmVlZCB0byBjcmVhdGUgYSBub3JtYWxpemUoKSBmdW5jdGlvbiBpbiBSLiBUaGlzDQpmdW5jdGlvbiB0YWtlcyBhIHZlY3RvciB4IG9mIG51bWVyaWMgdmFsdWVzLCBhbmQgZm9yIGVhY2ggdmFsdWUgaW4geCwgc3VidHJhY3RzIHRoZQ0KbWluaW11bSB2YWx1ZSBpbiB4IGFuZCBkaXZpZGVzIGJ5IHRoZSByYW5nZSBvZiB2YWx1ZXMgaW4geC4gRmluYWxseSwgdGhlIHJlc3VsdGluZw0KdmVjdG9yIGlzIHJldHVybmVkLiBUaGUgY29kZSBmb3IgdGhpcyBmdW5jdGlvbiBpcyBhcyBmb2xsb3dzOg0KDQpgYGB7cn0NCm5vcm1hbGl6ZSA8LSBmdW5jdGlvbih4KSB7DQogIHJldHVybiAoKHggLSBtaW4oeCkpIC8gKG1heCh4KSAtIG1pbih4KSkpDQp9DQpgYGANCg0KQWZ0ZXIgZXhlY3V0aW5nIHRoZSBwcmVjZWRpbmcgY29kZSwgdGhlIG5vcm1hbGl6ZSgpIGZ1bmN0aW9uIGlzIGF2YWlsYWJsZSBmb3IgdXNlIGluDQpSLiBMZXQncyB0ZXN0IHRoZSBmdW5jdGlvbiBvbiBhIGNvdXBsZSBvZiB2ZWN0b3JzOg0KDQpgYGB7cn0NCm5vcm1hbGl6ZShjKDEsIDIsIDMsIDQsIDUpKQ0KYGBgDQoNCmBgYHtyfQ0Kbm9ybWFsaXplKGMoMTAsIDIwLCAzMCwgNDAsIDUwKSkNCmBgYA0KDQpUaGUgZnVuY3Rpb24gYXBwZWFycyB0byBiZSB3b3JraW5nIGNvcnJlY3RseS4gRGVzcGl0ZSB0aGUgZmFjdCB0aGF0IHRoZSB2YWx1ZXMgaW4gdGhlDQpzZWNvbmQgdmVjdG9yIGFyZSAxMCB0aW1lcyBsYXJnZXIgdGhhbiB0aGUgZmlyc3QgdmVjdG9yLCBhZnRlciBub3JtYWxpemF0aW9uLCB0aGV5IGJvdGgNCmFwcGVhciBleGFjdGx5IHRoZSBzYW1lLg0KDQpXZSBjYW4gbm93IGFwcGx5IHRoZSBub3JtYWxpemUoKSBmdW5jdGlvbiB0byB0aGUgbnVtZXJpYyBmZWF0dXJlcyBpbiBvdXIgZGF0YQ0KZnJhbWUuIFJhdGhlciB0aGFuIG5vcm1hbGl6aW5nIGVhY2ggb2YgdGhlIDMwIG51bWVyaWMgdmFyaWFibGVzIGluZGl2aWR1YWxseSwgd2UNCndpbGwgdXNlIG9uZSBvZiBSJ3MgZnVuY3Rpb25zIHRvIGF1dG9tYXRlIHRoZSBwcm9jZXNzLg0KDQpUaGUgbGFwcGx5KCkgZnVuY3Rpb24gdGFrZXMgYSBsaXN0IGFuZCBhcHBsaWVzIGEgc3BlY2lmaWVkIGZ1bmN0aW9uIHRvIGVhY2ggbGlzdA0KZWxlbWVudC4gQXMgYSBkYXRhIGZyYW1lIGlzIGEgbGlzdCBvZiBlcXVhbC1sZW5ndGggdmVjdG9ycywgd2UgY2FuIHVzZSBsYXBwbHkoKSB0bw0KYXBwbHkgbm9ybWFsaXplKCkgdG8gZWFjaCBmZWF0dXJlIGluIHRoZSBkYXRhIGZyYW1lLiBUaGUgZmluYWwgc3RlcCBpcyB0byBjb252ZXJ0IHRoZQ0KbGlzdCByZXR1cm5lZCBieSBsYXBwbHkoKSB0byBhIGRhdGEgZnJhbWUsIHVzaW5nIHRoZSBhcy5kYXRhLmZyYW1lKCkgZnVuY3Rpb24uIFRoZQ0KZnVsbCBwcm9jZXNzIGxvb2tzIGxpa2UgdGhpczoNCg0KYGBge3J9DQp3YmNkX24gPC0gYXMuZGF0YS5mcmFtZShsYXBwbHkod2JjZFsyOjMxXSwgbm9ybWFsaXplKSkNCmBgYA0KDQpJbiBwbGFpbiBFbmdsaXNoLCB0aGlzIGNvbW1hbmQgYXBwbGllcyB0aGUgbm9ybWFsaXplKCkgZnVuY3Rpb24gdG8gY29sdW1ucw0KMiB0aHJvdWdoIDMxIGluIHRoZSB3YmNkIGRhdGEgZnJhbWUsIGNvbnZlcnRzIHRoZSByZXN1bHRpbmcgbGlzdCB0byBhIGRhdGEgZnJhbWUsDQphbmQgYXNzaWducyBpdCB0aGUgbmFtZSB3YmNkX24uIFRoZSBfbiBzdWZmaXggaXMgdXNlZCBoZXJlIGFzIGEgcmVtaW5kZXIgdGhhdCB0aGUNCnZhbHVlcyBpbiB3YmNkIGhhdmUgYmVlbiBub3JtYWxpemVkLg0KDQpUbyBjb25maXJtIHRoYXQgdGhlIHRyYW5zZm9ybWF0aW9uIHdhcyBhcHBsaWVkIGNvcnJlY3RseSwgbGV0J3MgbG9vayBhdCBvbmUgdmFyaWFibGUncw0Kc3VtbWFyeSBzdGF0aXN0aWNzOg0KDQpgYGB7cn0NCnN1bW1hcnkod2JjZF9uJGFyZWFfbWVhbikNCmBgYA0KDQpBcyBleHBlY3RlZCwgdGhlIGFyZWFfbWVhbiB2YXJpYWJsZSwgd2hpY2ggb3JpZ2luYWxseSByYW5nZWQgZnJvbSAxNDMuNSB0byAyNTAxLjAsDQpub3cgcmFuZ2VzIGZyb20gMCB0byAxLg0KDQojRGF0YSBwcmVwYXJhdGlvbiAtIGNyZWF0aW5nIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGFzZXRzDQoNCkFsdGhvdWdoIGFsbCB0aGUgNTY5IGJpb3BzaWVzIGFyZSBsYWJlbGVkIHdpdGggYSBiZW5pZ24gb3IgbWFsaWduYW50IHN0YXR1cywgaXQgaXMgbm90DQp2ZXJ5IGludGVyZXN0aW5nIHRvIHByZWRpY3Qgd2hhdCB3ZSBhbHJlYWR5IGtub3cuIEFkZGl0aW9uYWxseSwgYW55IHBlcmZvcm1hbmNlDQptZWFzdXJlcyB3ZSBvYnRhaW4gZHVyaW5nIHRoZSB0cmFpbmluZyBtYXkgYmUgbWlzbGVhZGluZyBhcyB3ZSBkbyBub3Qga25vdyB0aGUNCmV4dGVudCB0byB3aGljaCBjYXNlcyBoYXZlIGJlZW4gb3ZlcmZpdHRlZCBvciBob3cgd2VsbCB0aGUgbGVhcm5lciB3aWxsIGdlbmVyYWxpemUNCnRvIHVuc2VlbiBjYXNlcy4gQSBtb3JlIGludGVyZXN0aW5nIHF1ZXN0aW9uIGlzIGhvdyB3ZWxsIG91ciBsZWFybmVyIHBlcmZvcm1zIG9uDQphIGRhdGFzZXQgb2YgdW5sYWJlbGVkIGRhdGEuIElmIHdlIGhhZCBhY2Nlc3MgdG8gYSBsYWJvcmF0b3J5LCB3ZSBjb3VsZCBhcHBseSBvdXINCmxlYXJuZXIgdG8gdGhlIG1lYXN1cmVtZW50cyB0YWtlbiBmcm9tIHRoZSBuZXh0IDEwMCBtYXNzZXMgb2YgdW5rbm93biBjYW5jZXINCnN0YXR1cywgYW5kIHNlZSBob3cgd2VsbCB0aGUgbWFjaGluZSBsZWFybmVyJ3MgcHJlZGljdGlvbnMgY29tcGFyZSB0byB0aGUgZGlhZ25vc2VzDQpvYnRhaW5lZCB1c2luZyBjb252ZW50aW9uYWwgbWV0aG9kcy4NCg0KSW4gdGhlIGFic2VuY2Ugb2Ygc3VjaCBkYXRhLCB3ZSBjYW4gc2ltdWxhdGUgdGhpcyBzY2VuYXJpbyBieSBkaXZpZGluZyBvdXIgZGF0YSBpbnRvDQp0d28gcG9ydGlvbnM6IGEgdHJhaW5pbmcgZGF0YXNldCB0aGF0IHdpbGwgYmUgdXNlZCB0byBidWlsZCB0aGUgay1OTiBtb2RlbCBhbmQgYSB0ZXN0DQpkYXRhc2V0IHRoYXQgd2lsbCBiZSB1c2VkIHRvIGVzdGltYXRlIHRoZSBwcmVkaWN0aXZlIGFjY3VyYWN5IG9mIHRoZSBtb2RlbC4gV2Ugd2lsbA0KdXNlIHRoZSBmaXJzdCA0NjkgcmVjb3JkcyBmb3IgdGhlIHRyYWluaW5nIGRhdGFzZXQgYW5kIHRoZSByZW1haW5pbmcgMTAwIHRvIHNpbXVsYXRlDQpuZXcgcGF0aWVudHMuDQoNClVzaW5nIHRoZSBkYXRhIGV4dHJhY3Rpb24gbWV0aG9kcyBnaXZlbiBpbiBDaGFwdGVyIDIsIE1hbmFnaW5nIGFuZCBVbmRlcnN0YW5kaW5nDQpEYXRhLCB3ZSB3aWxsIHNwbGl0IHRoZSB3YmNkX24gZGF0YSBmcmFtZSBpbnRvIHdiY2RfdHJhaW4gYW5kIHdiY2RfdGVzdDoNCg0KDQpgYGB7cn0NCndiY2RfdHJhaW4gPC0gd2JjZF9uWzE6NDY5LCBdDQpgYGANCg0KYGBge3J9DQp3YmNkX3Rlc3QgPC0gd2JjZF9uWzQ3MDo1NjksIF0NCmBgYA0KDQoNCklmIHRoZSBwcmVjZWRpbmcgY29tbWFuZHMgYXJlIGNvbmZ1c2luZywgcmVtZW1iZXIgdGhhdCBkYXRhIGlzIGV4dHJhY3RlZCBmcm9tIGRhdGENCmZyYW1lcyB1c2luZyB0aGUgW3JvdywgY29sdW1uXSBzeW50YXguIEEgYmxhbmsgdmFsdWUgZm9yIHRoZSByb3cgb3IgY29sdW1uIHZhbHVlDQppbmRpY2F0ZXMgdGhhdCBhbGwgdGhlIHJvd3Mgb3IgY29sdW1ucyBzaG91bGQgYmUgaW5jbHVkZWQuIEhlbmNlLCB0aGUgZmlyc3QgbGluZSBvZg0KY29kZSB0YWtlcyByb3dzIDEgdG8gNDY5IGFuZCBhbGwgY29sdW1ucywgYW5kIHRoZSBzZWNvbmQgbGluZSB0YWtlcyAxMDAgcm93cyBmcm9tDQo0NzAgdG8gNTY5IGFuZCBhbGwgY29sdW1ucy4NCg0KV2hlbiB3ZSBjb25zdHJ1Y3RlZCBvdXIgbm9ybWFsaXplZCB0cmFpbmluZyBhbmQgdGVzdCBkYXRhc2V0cywgd2UgZXhjbHVkZWQgdGhlDQp0YXJnZXQgdmFyaWFibGUsIGRpYWdub3Npcy4gRm9yIHRyYWluaW5nIHRoZSBrLU5OIG1vZGVsLCB3ZSB3aWxsIG5lZWQgdG8gc3RvcmUNCnRoZXNlIGNsYXNzIGxhYmVscyBpbiBmYWN0b3IgdmVjdG9ycywgc3BsaXQgYmV0d2VlbiB0aGUgdHJhaW5pbmcgYW5kIHRlc3QgZGF0YXNldHM6DQoNCmBgYHtyfQ0Kd2JjZF90cmFpbl9sYWJlbHMgPC0gd2JjZFsxOjQ2OSwgMV0NCmBgYA0KDQoNCmBgYHtyfQ0Kd2JjZF90ZXN0X2xhYmVscyA8LSB3YmNkWzQ3MDo1NjksIDFdDQoNCmBgYA0KDQoNClRoaXMgY29kZSB0YWtlcyB0aGUgZGlhZ25vc2lzIGZhY3RvciBpbiB0aGUgZmlyc3QgY29sdW1uIG9mIHRoZSB3YmNkIGRhdGEgZnJhbWUsIGFuZA0KY3JlYXRlcyB0aGUgdmVjdG9ycyB3YmNkX3RyYWluX2xhYmVscyBhbmQgd2JjZF90ZXN0X2xhYmVscy4gV2Ugd2lsbCB1c2UgdGhlc2UNCmluIHRoZSBuZXh0IHN0ZXBzIG9mIHRyYWluaW5nIGFuZCBldmFsdWF0aW5nIG91ciBjbGFzc2lmaWVyLg0KDQojI3RyYWluaW5nIGEgbW9kZWwgb24gdGhlIGRhdGENCg0KRXF1aXBwZWQgd2l0aCBvdXIgdHJhaW5pbmcgZGF0YSBhbmQgbGFiZWxzIHZlY3Rvciwgd2UgYXJlIG5vdyByZWFkeSB0byBjbGFzc2lmeSBvdXINCnVua25vd24gcmVjb3Jkcy4gRm9yIHRoZSBrLU5OIGFsZ29yaXRobSwgdGhlIHRyYWluaW5nIHBoYXNlIGFjdHVhbGx5IGludm9sdmVzIG5vDQptb2RlbCBidWlsZGluZzsgdGhlIHByb2Nlc3Mgb2YgdHJhaW5pbmcgYSBsYXp5IGxlYXJuZXIgbGlrZSBrLU5OIHNpbXBseSBpbnZvbHZlcw0Kc3RvcmluZyB0aGUgaW5wdXQgZGF0YSBpbiBhIHN0cnVjdHVyZWQgZm9ybWF0Lg0KDQpUbyBjbGFzc2lmeSBvdXIgdGVzdCBpbnN0YW5jZXMsIHdlIHdpbGwgdXNlIGEgay1OTiBpbXBsZW1lbnRhdGlvbiBmcm9tIHRoZSBjbGFzcw0KcGFja2FnZSwgd2hpY2ggcHJvdmlkZXMgYSBzZXQgb2YgYmFzaWMgUiBmdW5jdGlvbnMgZm9yIGNsYXNzaWZpY2F0aW9uLiBJZiB0aGlzIHBhY2thZ2UNCmlzIG5vdCBhbHJlYWR5IGluc3RhbGxlZCBvbiB5b3VyIHN5c3RlbSwgeW91IGNhbiBpbnN0YWxsIGl0IGJ5IHR5cGluZzoNCg0KYGBge3J9DQppbnN0YWxsLnBhY2thZ2VzKCJjbGFzcyIpDQpgYGANCg0KDQpUbyBsb2FkIHRoZSBwYWNrYWdlIGR1cmluZyBhbnkgc2Vzc2lvbiBpbiB3aGljaCB5b3Ugd2lzaCB0byB1c2UgdGhlIGZ1bmN0aW9ucywNCnNpbXBseSBlbnRlciB0aGUgbGlicmFyeShjbGFzcykgY29tbWFuZC4NCg0KYGBge3J9DQpsaWJyYXJ5KGNsYXNzKQ0KYGBgDQoNCg0KVGhlIGtubigpIGZ1bmN0aW9uIGluIHRoZSBjbGFzcyBwYWNrYWdlIHByb3ZpZGVzIGEgc3RhbmRhcmQsIGNsYXNzaWMNCmltcGxlbWVudGF0aW9uIG9mIHRoZSBrLU5OIGFsZ29yaXRobS4gRm9yIGVhY2ggaW5zdGFuY2UgaW4gdGhlIHRlc3QgZGF0YSwgdGhlDQpmdW5jdGlvbiB3aWxsIGlkZW50aWZ5IHRoZSBrLU5lYXJlc3QgTmVpZ2hib3JzLCB1c2luZyBFdWNsaWRlYW4gZGlzdGFuY2UsIHdoZXJlIGsgaXMNCmEgdXNlci1zcGVjaWZpZWQgbnVtYmVyLiBUaGUgdGVzdCBpbnN0YW5jZSBpcyBjbGFzc2lmaWVkIGJ5IHRha2luZyBhICJ2b3RlIiBhbW9uZyB0aGUNCmstTmVhcmVzdCBOZWlnaGJvcnMtc3BlY2lmaWNhbGx5LCB0aGlzIGludm9sdmVzIGFzc2lnbmluZyB0aGUgY2xhc3Mgb2YgdGhlIG1ham9yaXR5IG9mDQp0aGUgayBuZWlnaGJvcnMuIEEgdGllIHZvdGUgaXMgYnJva2VuIGF0IHJhbmRvbS4NCg0KV2Ugbm93IGhhdmUgbmVhcmx5IGV2ZXJ5dGhpbmcgdGhhdCB3ZSBuZWVkIHRvIGFwcGx5IHRoZSBrLU5OIGFsZ29yaXRobSB0bw0KdGhpcyBkYXRhLiBXZSd2ZSBzcGxpdCBvdXIgZGF0YSBpbnRvIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGFzZXRzLCBlYWNoIHdpdGggZXhhY3RseSB0aGUNCnNhbWUgbnVtZXJpYyBmZWF0dXJlcy4gVGhlIGxhYmVscyBmb3IgdGhlIHRyYWluaW5nIGRhdGEgYXJlIHN0b3JlZCBpbiBhIHNlcGFyYXRlIGZhY3Rvcg0KdmVjdG9yLiBUaGUgb25seSByZW1haW5pbmcgcGFyYW1ldGVyIGlzIGssIHdoaWNoIHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIG5laWdoYm9ycw0KdG8gaW5jbHVkZSBpbiB0aGUgdm90ZS4NCg0KQXMgb3VyIHRyYWluaW5nIGRhdGEgaW5jbHVkZXMgNDY5IGluc3RhbmNlcywgd2UgbWlnaHQgdHJ5IGsgPSAyMSwgYW4gb2RkIG51bWJlcg0Kcm91Z2hseSBlcXVhbCB0byB0aGUgc3F1YXJlIHJvb3Qgb2YgNDY5LiBXaXRoIGEgdHdvLWNhdGVnb3J5IG91dGNvbWUsIHVzaW5nIGFuIG9kZA0KbnVtYmVyIGVsaW1pbmF0ZXMgdGhlIGNoYW5jZSBvZiBlbmRpbmcgd2l0aCBhIHRpZSB2b3RlLg0KDQpOb3cgd2UgY2FuIHVzZSB0aGUga25uKCkgZnVuY3Rpb24gdG8gY2xhc3NpZnkgdGhlIHRlc3QgZGF0YToNCg0KYGBge3J9DQp3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LCBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrID0gMjEpDQpgYGANCg0KDQpUaGUga25uKCkgZnVuY3Rpb24gcmV0dXJucyBhIGZhY3RvciB2ZWN0b3Igb2YgcHJlZGljdGVkIGxhYmVscyBmb3IgZWFjaCBvZiB0aGUNCmV4YW1wbGVzIGluIHRoZSB0ZXN0IGRhdGFzZXQsIHdoaWNoIHdlIGhhdmUgYXNzaWduZWQgdG8gd2JjZF90ZXN0X3ByZWQuDQoNCiMjZXZhbHVhdGluZyBtb2RlbCBwZXJmb3JtYW5jZQ0KDQpUaGUgbmV4dCBzdGVwIG9mIHRoZSBwcm9jZXNzIGlzIHRvIGV2YWx1YXRlIGhvdyB3ZWxsIHRoZSBwcmVkaWN0ZWQgY2xhc3NlcyBpbiB0aGUgd2JjZF8NCnRlc3RfcHJlZCB2ZWN0b3IgbWF0Y2ggdXAgd2l0aCB0aGUga25vd24gdmFsdWVzIGluIHRoZSB3YmNkX3Rlc3RfbGFiZWxzIHZlY3Rvci4NClRvIGRvIHRoaXMsIHdlIGNhbiB1c2UgdGhlIENyb3NzVGFibGUoKSBmdW5jdGlvbiBpbiB0aGUgZ21vZGVscyBwYWNrYWdlLCB3aGljaA0Kd2FzIGludHJvZHVjZWQgaW4gQ2hhcHRlciAyLCBNYW5hZ2luZyBhbmQgVW5kZXJzdGFuZGluZyBEYXRhLiBJZiB5b3UgaGF2ZW4ndCBkb25lDQpzbyBhbHJlYWR5LCBwbGVhc2UgaW5zdGFsbCB0aGlzIHBhY2thZ2UsIHVzaW5nIHRoZSBpbnN0YWxsLnBhY2thZ2VzKCJnbW9kZWxzIikNCmNvbW1hbmQuDQoNCkFmdGVyIGxvYWRpbmcgdGhlIHBhY2thZ2Ugd2l0aCB0aGUgbGlicmFyeShnbW9kZWxzKSBjb21tYW5kLCB3ZSBjYW4NCmNyZWF0ZSBhIGNyb3NzIHRhYnVsYXRpb24gaW5kaWNhdGluZyB0aGUgYWdyZWVtZW50IGJldHdlZW4gdGhlIHR3byB2ZWN0b3JzLg0KU3BlY2lmeWluZyBwcm9wLmNoaXNxID0gRkFMU0Ugd2lsbCByZW1vdmUgdGhlIHVubmVjZXNzYXJ5IGNoaS1zcXVhcmUNCnZhbHVlcyBmcm9tIHRoZSBvdXRwdXQ6DQoNCmBgYHtyfQ0KQ3Jvc3NUYWJsZSh4ID0gd2JjZF90ZXN0X2xhYmVscywgeSA9IHdiY2RfdGVzdF9wcmVkLCBwcm9wLmNoaXNxPUZBTFNFKQ0KYGBgDQoNClRoZSBjZWxsIHBlcmNlbnRhZ2VzIGluIHRoZSB0YWJsZSBpbmRpY2F0ZSB0aGUgcHJvcG9ydGlvbiBvZiB2YWx1ZXMgdGhhdCBmYWxsIGludG8gZm91cg0KY2F0ZWdvcmllcy4gVGhlIHRvcC1sZWZ0IGNlbGwgaW5kaWNhdGVzIHRoZSB0cnVlIG5lZ2F0aXZlIHJlc3VsdHMuIFRoZXNlIDYxIG9mIDEwMCB2YWx1ZXMNCmFyZSBjYXNlcyB3aGVyZSB0aGUgbWFzcyB3YXMgYmVuaWduIGFuZCB0aGUgay1OTiBhbGdvcml0aG0gY29ycmVjdGx5IGlkZW50aWZpZWQgaXQNCmFzIHN1Y2guIFRoZSBib3R0b20tcmlnaHQgY2VsbCBpbmRpY2F0ZXMgdGhlIHRydWUgcG9zaXRpdmUgcmVzdWx0cywgd2hlcmUgdGhlIGNsYXNzaWZpZXINCmFuZCB0aGUgY2xpbmljYWxseSBkZXRlcm1pbmVkIGxhYmVsIGFncmVlIHRoYXQgdGhlIG1hc3MgaXMgbWFsaWduYW50LiBBIHRvdGFsIG9mIDM3IG9mDQoxMDAgcHJlZGljdGlvbnMgd2VyZSB0cnVlIHBvc2l0aXZlcy4NCg0KVGhlIGNlbGxzIGZhbGxpbmcgb24gdGhlIG90aGVyIGRpYWdvbmFsIGNvbnRhaW4gY291bnRzIG9mIGV4YW1wbGVzIHdoZXJlIHRoZSBrLU5ODQphcHByb2FjaCBkaXNhZ3JlZWQgd2l0aCB0aGUgdHJ1ZSBsYWJlbC4gVGhlIHR3byBleGFtcGxlcyBpbiB0aGUgbG93ZXItbGVmdCBjZWxsIGFyZQ0KZmFsc2UgbmVnYXRpdmUgcmVzdWx0czsgaW4gdGhpcyBjYXNlLCB0aGUgcHJlZGljdGVkIHZhbHVlIHdhcyBiZW5pZ24sIGJ1dCB0aGUgdHVtb3INCndhcyBhY3R1YWxseSBtYWxpZ25hbnQuIEVycm9ycyBpbiB0aGlzIGRpcmVjdGlvbiBjb3VsZCBiZSBleHRyZW1lbHkgY29zdGx5IGFzIHRoZXkNCm1pZ2h0IGxlYWQgYSBwYXRpZW50IHRvIGJlbGlldmUgdGhhdCBzaGUgaXMgY2FuY2VyLWZyZWUsIGJ1dCBpbiByZWFsaXR5LCB0aGUgZGlzZWFzZSBtYXkNCmNvbnRpbnVlIHRvIHNwcmVhZC4gVGhlIHRvcC1yaWdodCBjZWxsIHdvdWxkIGNvbnRhaW4gdGhlIGZhbHNlIHBvc2l0aXZlIHJlc3VsdHMsIGlmDQp0aGVyZSB3ZXJlIGFueS4gVGhlc2UgdmFsdWVzIG9jY3VyIHdoZW4gdGhlIG1vZGVsIGNsYXNzaWZpZXMgYSBtYXNzIGFzIG1hbGlnbmFudCwNCmJ1dCBpbiByZWFsaXR5LCBpdCB3YXMgYmVuaWduLiBBbHRob3VnaCBzdWNoIGVycm9ycyBhcmUgbGVzcyBkYW5nZXJvdXMgdGhhbiBhIGZhbHNlDQpuZWdhdGl2ZSByZXN1bHQsIHRoZXkgc2hvdWxkIGFsc28gYmUgYXZvaWRlZCBhcyB0aGV5IGNvdWxkIGxlYWQgdG8gYWRkaXRpb25hbCBmaW5hbmNpYWwNCmJ1cmRlbiBvbiB0aGUgaGVhbHRoIGNhcmUgc3lzdGVtIG9yIGFkZGl0aW9uYWwgc3RyZXNzIGZvciB0aGUgcGF0aWVudCBhcyBhZGRpdGlvbmFsDQp0ZXN0cyBvciB0cmVhdG1lbnQgbWF5IGhhdmUgdG8gYmUgcHJvdmlkZWQuDQpUaGlzIGlzIGFuIFtSIE1hcmtkb3duXShodHRwOi8vcm1hcmtkb3duLnJzdHVkaW8uY29tKSBOb3RlYm9vay4gV2hlbiB5b3UgZXhlY3V0ZSBjb2RlIHdpdGhpbiB0aGUgbm90ZWJvb2ssIHRoZSByZXN1bHRzIGFwcGVhciBiZW5lYXRoIHRoZSBjb2RlLiANCg0KDQpBIHRvdGFsIG9mIDIgb3V0IG9mIDEwMCwgb3IgMiBwZXJjZW50IG9mIG1hc3NlcyB3ZXJlIGluY29ycmVjdGx5IGNsYXNzaWZpZWQgYnkgdGhlIGstTk4NCmFwcHJvYWNoLiBXaGlsZSA5OCBwZXJjZW50IGFjY3VyYWN5IHNlZW1zIGltcHJlc3NpdmUgZm9yIGEgZmV3IGxpbmVzIG9mIFIgY29kZSwNCndlIG1pZ2h0IHRyeSBhbm90aGVyIGl0ZXJhdGlvbiBvZiB0aGUgbW9kZWwgdG8gc2VlIHdoZXRoZXIgd2UgY2FuIGltcHJvdmUgdGhlDQpwZXJmb3JtYW5jZSBhbmQgcmVkdWNlIHRoZSBudW1iZXIgb2YgdmFsdWVzIHRoYXQgaGF2ZSBiZWVuIGluY29ycmVjdGx5IGNsYXNzaWZpZWQsDQpwYXJ0aWN1bGFybHkgYmVjYXVzZSB0aGUgZXJyb3JzIHdlcmUgZGFuZ2Vyb3VzIGZhbHNlIG5lZ2F0aXZlcy4NCg0KIyNpbXByb3ZpbmcgbW9kZWwgcGVyZm9ybWFuY2UNCg0KV2Ugd2lsbCBhdHRlbXB0IHR3byBzaW1wbGUgdmFyaWF0aW9ucyBvbiBvdXIgcHJldmlvdXMgY2xhc3NpZmllci4gRmlyc3QsIHdlIHdpbGwNCmVtcGxveSBhbiBhbHRlcm5hdGl2ZSBtZXRob2QgZm9yIHJlc2NhbGluZyBvdXIgbnVtZXJpYyBmZWF0dXJlcy4gU2Vjb25kLCB3ZQ0Kd2lsbCB0cnkgc2V2ZXJhbCBkaWZmZXJlbnQgdmFsdWVzIGZvciBrLg0KDQoNCiMjVHJhbnNmb3JtYXRpb24gLSB6LXNjb3JlIHN0YW5kYXJkaXphdGlvbg0KDQpBbHRob3VnaCBub3JtYWxpemF0aW9uIGlzIHRyYWRpdGlvbmFsbHkgdXNlZCBmb3Igay1OTiBjbGFzc2lmaWNhdGlvbiwgaXQgbWF5DQpub3QgYWx3YXlzIGJlIHRoZSBtb3N0IGFwcHJvcHJpYXRlIHdheSB0byByZXNjYWxlIGZlYXR1cmVzLiBTaW5jZSB0aGUgei1zY29yZQ0Kc3RhbmRhcmRpemVkIHZhbHVlcyBoYXZlIG5vIHByZWRlZmluZWQgbWluaW11bSBhbmQgbWF4aW11bSwgZXh0cmVtZSB2YWx1ZXMNCmFyZSBub3QgY29tcHJlc3NlZCB0b3dhcmRzIHRoZSBjZW50ZXIuIE9uZSBtaWdodCBzdXNwZWN0IHRoYXQgd2l0aCBhIG1hbGlnbmFudA0KdHVtb3IsIHdlIG1pZ2h0IHNlZSBzb21lIHZlcnkgZXh0cmVtZSBvdXRsaWVycyBhcyB0aGUgdHVtb3JzIGdyb3cgdW5jb250cm9sbGFibHkuDQpJdCBtaWdodCwgdGhlcmVmb3JlLCBiZSByZWFzb25hYmxlIHRvIGFsbG93IHRoZSBvdXRsaWVycyB0byBiZSB3ZWlnaHRlZCBtb3JlIGhlYXZpbHkgaW4NCnRoZSBkaXN0YW5jZSBjYWxjdWxhdGlvbi4gTGV0J3Mgc2VlIHdoZXRoZXIgei1zY29yZSBzdGFuZGFyZGl6YXRpb24gY2FuIGltcHJvdmUgb3VyDQpwcmVkaWN0aXZlIGFjY3VyYWN5Lg0KDQpUbyBzdGFuZGFyZGl6ZSBhIHZlY3Rvciwgd2UgY2FuIHVzZSB0aGUgUidzIGJ1aWx0LWluIHNjYWxlKCkgZnVuY3Rpb24sIHdoaWNoLCBieQ0KZGVmYXVsdCwgcmVzY2FsZXMgdmFsdWVzIHVzaW5nIHRoZSB6LXNjb3JlIHN0YW5kYXJkaXphdGlvbi4gVGhlIHNjYWxlKCkgZnVuY3Rpb24NCm9mZmVycyB0aGUgYWRkaXRpb25hbCBiZW5lZml0IHRoYXQgaXQgY2FuIGJlIGFwcGxpZWQgZGlyZWN0bHkgdG8gYSBkYXRhIGZyYW1lLCBzbyB3ZSBjYW4NCmF2b2lkIHRoZSB1c2Ugb2YgdGhlIGxhcHBseSgpIGZ1bmN0aW9uLiBUbyBjcmVhdGUgYSB6LXNjb3JlIHN0YW5kYXJkaXplZCB2ZXJzaW9uIG9mDQp0aGUgd2JjZCBkYXRhLCB3ZSBjYW4gdXNlIHRoZSBmb2xsb3dpbmcgY29tbWFuZDoNCg0KYGBge3J9DQp3YmNkX3ogPC0gYXMuZGF0YS5mcmFtZShzY2FsZSh3YmNkWy0xXSkpDQpgYGANCg0KVGhpcyBjb21tYW5kIHJlc2NhbGVzIGFsbCB0aGUgZmVhdHVyZXMsIHdpdGggdGhlIGV4Y2VwdGlvbiBvZiBkaWFnbm9zaXMgYW5kIHN0b3Jlcw0KdGhlIHJlc3VsdCBhcyB0aGUgd2JjZF96IGRhdGEgZnJhbWUuIFRoZSBfeiBzdWZmaXggaXMgYSByZW1pbmRlciB0aGF0IHRoZSB2YWx1ZXMgd2VyZQ0Kei1zY29yZSB0cmFuc2Zvcm1lZC4NCg0KVG8gY29uZmlybSB0aGF0IHRoZSB0cmFuc2Zvcm1hdGlvbiB3YXMgYXBwbGllZCBjb3JyZWN0bHksIHdlIGNhbiBsb29rIGF0IHRoZQ0Kc3VtbWFyeSBzdGF0aXN0aWNzOg0KDQpgYGB7cn0NCnN1bW1hcnkod2JjZF96JGFyZWFfbWVhbikNCmBgYA0KDQpUaGUgbWVhbiBvZiBhIHotc2NvcmUgc3RhbmRhcmRpemVkIHZhcmlhYmxlIHNob3VsZCBhbHdheXMgYmUgemVybywgYW5kIHRoZSByYW5nZQ0Kc2hvdWxkIGJlIGZhaXJseSBjb21wYWN0LiBBIHotc2NvcmUgZ3JlYXRlciB0aGFuIDMgb3IgbGVzcyB0aGFuIC0zIGluZGljYXRlcyBhbg0KZXh0cmVtZWx5IHJhcmUgdmFsdWUuIFdpdGggdGhpcyBpbiBtaW5kLCB0aGUgdHJhbnNmb3JtYXRpb24gc2VlbXMgdG8gaGF2ZSB3b3JrZWQuDQoNCkFzIHdlIGhhZCBkb25lIGVhcmxpZXIsIHdlIG5lZWQgdG8gZGl2aWRlIHRoZSBkYXRhIGludG8gdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cywgYW5kDQp0aGVuIGNsYXNzaWZ5IHRoZSB0ZXN0IGluc3RhbmNlcyB1c2luZyB0aGUga25uKCkgZnVuY3Rpb24uIFdlJ2xsIHRoZW4gY29tcGFyZSB0aGUNCnByZWRpY3RlZCBsYWJlbHMgdG8gdGhlIGFjdHVhbCBsYWJlbHMgdXNpbmcgQ3Jvc3NUYWJsZSgpOg0KDQoNCmBgYHtyfQ0Kd2JjZF90cmFpbiA8LSB3YmNkX3pbMTo0NjksIF0NCndiY2RfdGVzdCA8LSB3YmNkX3pbNDcwOjU2OSwgXQ0Kd2JjZF90cmFpbl9sYWJlbHMgPC0gd2JjZFsxOjQ2OSwgMV0NCndiY2RfdGVzdF9sYWJlbHMgPC0gd2JjZFs0NzA6NTY5LCAxXQ0Kd2JjZF90ZXN0X3ByZWQgPC0ga25uKHRyYWluID0gd2JjZF90cmFpbiwgdGVzdCA9IHdiY2RfdGVzdCwNCmNsID0gd2JjZF90cmFpbl9sYWJlbHMsIGsgPSAyMSkNCmBgYA0KDQpVbmZvcnR1bmF0ZWx5LCBpbiB0aGUgZm9sbG93aW5nIHRhYmxlLCB0aGUgcmVzdWx0cyBvZiBvdXIgbmV3IHRyYW5zZm9ybWF0aW9uIHNob3cgYQ0Kc2xpZ2h0IGRlY2xpbmUgaW4gYWNjdXJhY3kuIFRoZSBpbnN0YW5jZXMgd2hlcmUgd2UgaGFkIGNvcnJlY3RseSBjbGFzc2lmaWVkIDk4IHBlcmNlbnQNCm9mIGV4YW1wbGVzIHByZXZpb3VzbHksIHdlIGNsYXNzaWZpZWQgb25seSA5NSBwZXJjZW50IGNvcnJlY3RseSB0aGlzIHRpbWUuIE1ha2luZw0KbWF0dGVycyB3b3JzZSwgd2UgZGlkIG5vIGJldHRlciBhdCBjbGFzc2lmeWluZyB0aGUgZGFuZ2Vyb3VzIGZhbHNlIG5lZ2F0aXZlczoNCg0KDQpgYGB7cn0NCkNyb3NzVGFibGUoeCA9IHdiY2RfdGVzdF9sYWJlbHMsIHkgPSB3YmNkX3Rlc3RfcHJlZCwgcHJvcC5jaGlzcSA9IEZBTFNFKQ0KYGBgDQoNCg0KIyNUZXN0aW5nIGFsdGVybmF0aXZlIHZhbHVlcyBvZiBrDQoNCldlIG1heSBiZSBhYmxlIGRvIGV2ZW4gYmV0dGVyIGJ5IGV4YW1pbmluZyBwZXJmb3JtYW5jZSBhY3Jvc3MgdmFyaW91cyBrIHZhbHVlcy4NClVzaW5nIHRoZSBub3JtYWxpemVkIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGFzZXRzLCB0aGUgc2FtZSAxMDAgcmVjb3JkcyB3ZXJlIGNsYXNzaWZpZWQNCnVzaW5nIHNldmVyYWwgZGlmZmVyZW50IGsgdmFsdWVzLiBUaGUgbnVtYmVyIG9mIGZhbHNlIG5lZ2F0aXZlcyBhbmQgZmFsc2UgcG9zaXRpdmVzIGFyZQ0Kc2hvd24gZm9yIGVhY2ggaXRlcmF0aW9uDQoNCkFsdGhvdWdoIHRoZSBjbGFzc2lmaWVyIHdhcyBuZXZlciBwZXJmZWN0LCB0aGUgMS1OTiBhcHByb2FjaCB3YXMgYWJsZSB0byBhdm9pZA0Kc29tZSBvZiB0aGUgZmFsc2UgbmVnYXRpdmVzIGF0IHRoZSBleHBlbnNlIG9mIGFkZGluZyBmYWxzZSBwb3NpdGl2ZXMuIEl0IGlzIGltcG9ydGFudCB0bw0Ka2VlcCBpbiBtaW5kLCBob3dldmVyLCB0aGF0IGl0IHdvdWxkIGJlIHVud2lzZSB0byB0YWlsb3Igb3VyIGFwcHJvYWNoIHRvbyBjbG9zZWx5IHRvDQpvdXIgdGVzdCBkYXRhOyBhZnRlciBhbGwsIGEgZGlmZmVyZW50IHNldCBvZiAxMDAgcGF0aWVudCByZWNvcmRzIGlzIGxpa2VseSB0byBiZSBzb21ld2hhdA0KZGlmZmVyZW50IGZyb20gdGhvc2UgdXNlZCB0byBtZWFzdXJlIG91ciBwZXJmb3JtYW5jZS4NCg0KI0VPRg0KDQojDQo=