Adapted from the AUCell vignette and the cell-type-ewings module that is part of the Open Single-cell Pediatric Cancer Atlas project.

Objectives

  • Introduce the AUCell R package
  • Illustrate how AUC values are calculated
  • Demonstrate how AUC values can be used for cell assignment and plotting

In this notebook, we’ll demonstrate how to use the AUCell method, introduced in Aibar et al. 2017..

We can use AUCell when we are interested in a gene set’s relative expression or activity in an individual cell. Gene sets can come from a curated collection of prior knowledge, like the Hallmark collection we used in the last notebook, or we can use our own custom gene sets (e.g., a set of marker genes for a cell type of interest).

A nice feature of AUCell is that it is based on ranking genes from highest to lowest expression value in an individual cell, which is helpful in the following ways (AUCell vignette):

  • It can take a number of different values as input (e.g., raw counts, TPM)
  • It compensates for differences in library size, where something like averaging raw count values of genes in a gene set would not
  • It scales to larger datasets, since creating rankings is not as resource-intensive as something like permutation testing, and we could split up the object into subsets of cells if needed

AUCell calculates the area under the recovery curve (AUC), which “represents the proportion of expressed genes in the signature and their relative expression value compared to the other genes within the cell” (Aibar et al. 2017.). We will visualize some recovery curves in the notebook to give you a better intuition about the AUC and its meaning.

The AUC values we get out of AUCell can be used in a number of ways (Aibar et al. 2017.):

  • As continuous values we can use for visualization or clustering
  • For binary assignment (i.e., “on” and “off” or “expressed” and “not expressed”) if we pick a threshold either automatically using built-in functionality or manually by inspecting the distribution of scores ourselves

We will use an snRNA-seq of a Ewing sarcoma sample from the SCPCP000015 project on the Single-cell Pediatric Cancer Atlas Portal and two relevant gene sets from the Molecular Signatures Database (MSigDB) to demonstrate this method.

Set up

Libraries

# We will be loading a SingleCellExperiment object into our environment but don't need to see the startup messages
suppressPackageStartupMessages({
  library(SingleCellExperiment)
})
Warning: replacing previous import 'S4Arrays::makeNindexFromArrayViewport' by
'DelayedArray::makeNindexFromArrayViewport' when loading 'SummarizedExperiment'
# Library we'll use for the gene set analysis itself
library(AUCell)

# Libraries for accessing and working with gene sets
library(GSEABase)
Loading required package: annotate
Loading required package: AnnotationDbi
Loading required package: XML
Loading required package: graph

Attaching package: 'graph'
The following object is masked from 'package:XML':

    addNode
library(msigdbr)

Directories and files

Directories

# Input data 
ewing_data_dir <- fs::path("data", "ewing-sarcoma")
processed_dir <- fs::path(ewing_data_dir, "processed")

# Directory for holding pathway analysis results
analysis_dir <- fs::path("analysis", "ewing-sarcoma", "pathway-analysis")
# Create if it doesn't exist yet
fs::dir_create(analysis_dir)

Files

The input will be a SingleCellExperiment for an individual Ewing sarcoma library.

sce_file <- fs::path(processed_dir, 
                     "SCPCS000490", 
                     "SCPCL000822_processed.rds")

We will save the AUCell results as a table in the analysis directory.

output_file <- fs::path(analysis_dir,
                        "ewing_sarcoma_aucell_results.tsv")

Functions

The source() function allows us to load in custom functions we saved in an .R file.

source(fs::path("util", "aucell_functions.R"))

This loads one custom function, called plot_recovery_curve(), into our environment. This function is adapted from the AUCell vignette.

Set up gene sets

We are going to use two gene sets pertaining to Ewing sarcoma.

We would expect both of these gene sets to have high expression in tumor cells.

# Create a named vector with the relevant gene set names
ewing_gene_set_names <- c(zhang = "ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION",
                          riggi = "RIGGI_EWING_SARCOMA_PROGENITOR_UP")

ewing_gene_set_names
                               zhang                                riggi 
"ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION"  "RIGGI_EWING_SARCOMA_PROGENITOR_UP" 
ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION
RIGGI_EWING_SARCOMA_PROGENITOR_UP

These gene sets come from the C2 gene set collection from MSigDB. Let’s retrieve them using msigdbr().

ewing_gene_sets_df <- msigdbr(species = "Homo sapiens",
                              category = "C2",
                              subcategory = "CGP") |>
  dplyr::filter(gs_name %in% ewing_gene_set_names)

AUCell uses gene sets in a particular format that comes from the GSEABase package. We need to create a GeneSetCollection.

ewing_gene_set_collection <- ewing_gene_set_names |>
  purrr::map(
    # For each gene set
    \(gene_set_name) {
      ewing_gene_sets_df |>
        # Subset to the rows in that gene set
        dplyr::filter(gs_name == gene_set_name) |>
        # Grab the Ensembl gene identifiers
        dplyr::pull(ensembl_gene) |>
        # Create a GeneSet object
        GeneSet(setName = gene_set_name,
                geneIdType = ENSEMBLIdentifier())
    }
  ) |>
  # Turn the list of GeneSet objects into a GeneSet collection
  GeneSetCollection()

Read in and prepare SingleCellExperiment

sce <- readr::read_rds(sce_file)

The AUCell functions takes an expression matrix with genes as rows and cells as column. We can extract a counts matrix in sparse format for use with AUCell.

# Extract counts matrix
counts_matrix <- counts(sce)

There may be genes in our gene set that do not appear in the SingleCellExperiment object. We can remove them using the subsetGeneSets() function.

# Remove genes from gene sets if they are not in the SCE
ewing_gene_set_collection <- subsetGeneSets(ewing_gene_set_collection,
                                            rownames(counts_matrix))

AUCell

AUCell relies on ranking genes from highest to lowest expression value to calculate the AUC. The AUC is the area under the recovery curve, which captures the number of genes in a gene set that are present in the rankings above some threshold (i.e., it is the area under the curve to the left of this gene rank). By default, the top 5% of genes are used as the threshold.

Some genes will not be detected (i.e., have 0 counts). Genes can also have the same expression level (i.e., ties). These undetected genes and ties will be randomly ordered in our ranking. To make our rankings – and therefore results – reproducible, we will set a seed.

set.seed(2024)

Cell ranking

The first step in AUCell is to rank genes for each cell from highest to lowest expression value. We can do this using the AUCell_buildRankings() function, which will output a visualization showing the distribution of the number of genes detected in the cells in our SingleCellExperiment object.

cell_rankings <- AUCell_buildRankings(counts_matrix)
Quantiles for the number of genes detected by cell: 
(Non-detected genes are shuffled at the end of the ranking. Keep it in mind when choosing the threshold for calculating the AUC).

    min      1%      5%     10%     50%    100% 
 213.00  465.76  795.80 1102.20 2238.00 6608.00 

The AUCell authors recommend making sure most cells have at least the number of genes we will use as the max rank to calculate the AUC.

The AUC max rank value tells AUCell the cutoff in the gene rankings to use for calculating AUC; we will visualize this curve and max rank in just a moment. If we picked a max rank higher than the number of genes detected in most cells, the non-detected genes that are randomly ordered would play an outsized role in our AUC values.

By default, the max rank is the top 5% highest expressed genes. We can calculate the default max rank by taking into account the number of genes.

nrow(cell_rankings) * 0.05
[1] 3015.95

This number is probably too high, given the distribution of the number of genes detected by cell we visualized with AUCell_buildRankings().

What if we chose a 1% threshold?

nrow(cell_rankings) * 0.01
[1] 603.19

That is probably a more reasonable choice for this dataset.

We can use a function called ceiling() to round this and save it to a variable for later use.

auc_max_rank <- ceiling(nrow(cell_rankings) * 0.01)

Plotting AUC

The AUC values we get out of AUCell are the area under a recovery curve and estimate the proportion of genes in the gene set that are highly expressed (i.e., highly ranked).

Let’s plot the recovery curve for a cell with high AUC and a cell with low AUC to get a better intuition about AUC values. Earlier, we loaded a custom function we adapted from the AUCell vignette called plot_recovery_curve() with source().

First, we’ll start with a cell with a high AUC. We picked this barcode ahead of time when we wrote the notebook.

plot_recovery_curve(cell_rankings,
                    ewing_gene_set_collection,
                    gene_set_name = "ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION",
                    barcode = "CTGAGCGGTCTTTATC",
                    auc_max_rank = auc_max_rank)  # 1% threshold 

The x-axis is the gene ranks for all genes. The y-axis is the number of genes in the signature at a given point in the gene ranking – the line will rise when a gene in the gene set is encountered in the ranking from highest to lowest. The AUC is the area under this recovery curve at the max rank threshold chosen for this dataset.

Now, let’s look at an example with a low AUC.

plot_recovery_curve(cell_rankings,
                    ewing_gene_set_collection,
                    gene_set_name = "ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION",
                    barcode = "AGATAGAGTCACAATC",
                    auc_max_rank = auc_max_rank)  # 1% threshold

Far fewer genes in the gene set are ranked above the threshold, yielding a lower AUC value.

Calculating the AUC

Once we have the rankings, we can calculate the AUC scores for both gene sets in all cells with the AUCell_calcAUC() function.

cell_auc <- AUCell_calcAUC(geneSets = ewing_gene_set_collection, 
                           rankings = cell_rankings,
                           aucMaxRank = auc_max_rank)

This function returns an aucellResults object.

str(cell_auc)
Formal class 'aucellResults' [package "AUCell"] with 6 slots
  ..@ nGenesDetected : num(0) 
  ..@ colData        :Formal class 'DFrame' [package "S4Vectors"] with 6 slots
  .. .. ..@ rownames       : chr [1:4277] "AAGCATCTCGTTGCCT" "CTGTATTTCCAAGAGG" "CAGCAGCTCCTCAGAA" "AGGTCTAAGGGACTGT" ...
  .. .. ..@ nrows          : int 4277
  .. .. ..@ elementType    : chr "ANY"
  .. .. ..@ elementMetadata: NULL
  .. .. ..@ metadata       : list()
  .. .. ..@ listData       : Named list()
  ..@ assays         :Formal class 'SimpleAssays' [package "SummarizedExperiment"] with 1 slot
  .. .. ..@ data:Formal class 'SimpleList' [package "S4Vectors"] with 4 slots
  .. .. .. .. ..@ listData       :List of 1
  .. .. .. .. .. ..$ AUC: num [1:2, 1:4277] 0.1103 0.1206 0.0352 0.0538 0.1671 ...
  .. .. .. .. .. .. ..- attr(*, "dimnames")=List of 2
  .. .. .. .. .. .. .. ..$ gene sets: chr [1:2] "ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION" "RIGGI_EWING_SARCOMA_PROGENITOR_UP"
  .. .. .. .. .. .. .. ..$ cells    : chr [1:4277] "AAGCATCTCGTTGCCT" "CTGTATTTCCAAGAGG" "CAGCAGCTCCTCAGAA" "AGGTCTAAGGGACTGT" ...
  .. .. .. .. ..@ elementType    : chr "ANY"
  .. .. .. .. ..@ elementMetadata: NULL
  .. .. .. .. ..@ metadata       : list()
  ..@ NAMES          : chr [1:2] "ZHANG_TARGETS_OF_EWSR1_FLI1_FUSION" "RIGGI_EWING_SARCOMA_PROGENITOR_UP"
  ..@ elementMetadata:Formal class 'DFrame' [package "S4Vectors"] with 6 slots
  .. .. ..@ rownames       : NULL
  .. .. ..@ nrows          : int 2
  .. .. ..@ elementType    : chr "ANY"
  .. .. ..@ elementMetadata: NULL
  .. .. ..@ metadata       : list()
  .. .. ..@ listData       : Named list()
  ..@ metadata       : list()

It can be much more convenient to work with this in a tabular format.

# Extract AUC
auc_df <- cell_auc@assays@data$AUC |>
  # Transpose
  t() |>
  # Convert to data frame
  as.data.frame() |>
  # Make the barcodes a column
  tibble::rownames_to_column("barcodes") 

# Look at first few rows
head(auc_df)

Assignments

AUCell can assign cells as having an active gene set or not by picking a threshold automatically. We’ll explore these in a later plot, but for now, let’s calculate the threshold and assign cells with AUCell_exploreThresholds().

auc_assignments <- AUCell_exploreThresholds(cell_auc, 
                                            plotHist = FALSE, 
                                            assignCells = TRUE)

We’re going to plot the distribution of AUC values with ggplot2, so we will want the AUC values in a longer format.

auc_plotting_df <- auc_df |>
  tidyr::pivot_longer(!barcodes,
                      names_to = "gene_set",
                      values_to = "auc") |>
  dplyr::mutate(
    # Create a new logical column called assigned
    assigned = dplyr::case_when(
      # For Zhang gene set rows, set to TRUE when the barcode is in the 
      # assignment list
      gene_set == ewing_gene_set_names[["zhang"]] & 
        barcodes %in% auc_assignments[[ewing_gene_set_names[["zhang"]]]]$assignment ~ TRUE,
      # For Riggi gene set rows, set to TRUE when the barcode is in the 
      # assignment list
      gene_set == ewing_gene_set_names[["riggi"]] & 
        barcodes %in% auc_assignments[[ewing_gene_set_names[["riggi"]]]]$assignment ~ TRUE,
      # Otherwise, set to FALSE
      .default = FALSE
    )
  )

auc_plotting_df

To draw vertical lines representing the automatically chosen threshold, we can create a separate data frame.

auc_threshold_df <- data.frame(
  gene_set = ewing_gene_set_names,
  # Grab thresholds associated with each gene set from assignements object
  threshold = c(auc_assignments[[ewing_gene_set_names["zhang"]]]$aucThr$selected, 
                auc_assignments[[ewing_gene_set_names["riggi"]]]$aucThr$selected)
)

auc_threshold_df

Now let’s make a density plot, plotting the density of the assigned and unassigned cells separately and drawing a vertical line for the threshold.

auc_plotting_df |>
  ggplot2::ggplot(
    ggplot2::aes(
      x = auc,  # AUC values
      color = assigned,  # Group by assignment
      fill = assigned,   # Group by assignment
    )
  ) +
  ggplot2::geom_density(alpha = 0.2) +
  # Draw a vertical dotted line showing the threshold for each gene set
  ggplot2::geom_vline(data = auc_threshold_df,
                      mapping = ggplot2::aes(xintercept = threshold),
                      lty = 2) +
  # Plot each gene set in its own facet
  ggplot2::facet_grid(cols = ggplot2::vars(gene_set)) +
  # Use a built-in theme
  ggplot2::theme_bw()

For these particular gene sets, the AUC values appear to be bimodally distributed, and we can easily identify cells where the genes are highly expressed.

Let’s write this table to the output file.

auc_plotting_df |> 
  readr::write_tsv(output_file)

UMAPs

Adding AUC to colData

We can also add the AUC values back into the SingleCellExperiment for convenience, e.g., for plotting. We’ll add it to the existing colData.

First, let’s rename the gene set columns to something more easily typed.

auc_df <- auc_df |>
  # Use shorter names
  dplyr::rename(zhang_auc = ewing_gene_set_names[["zhang"]],
                riggi_auc = ewing_gene_set_names[["riggi"]])

And join it to the existing colData.

# Extract the existing colData, and left join it with the AUC values by the
# barcodes
coldata_df <- colData(sce) |>
  as.data.frame() |>
  dplyr::left_join(
    auc_df,
    by = "barcodes"
  )

Now, we’re ready to add it back to the object.

# We need to save this as a DataFrame
colData(sce) <- DataFrame(
  coldata_df,
  row.names = colData(sce)$barcodes
)

Plotting UMAPs

We can use the plotUMAP() function from the scater package to plot a UMAP with the points colored by the AUC value

scater::plotUMAP(sce, colour_by = "zhang_auc") +
  # Use the gene set name, replacing underscores with spaces
  ggplot2::ggtitle(stringr::str_replace_all(ewing_gene_set_names[["zhang"]], 
                                            "\\_", 
                                            " "))

Let’s color the points by the AUC values for the other gene set.

scater::plotUMAP(sce, colour_by = "riggi_auc") + 
  ggplot2::ggtitle(stringr::str_replace_all(ewing_gene_set_names[["riggi"]], 
                                            "\\_", 
                                            " "))

We would want to do something more formal to confirm, but it seems like the same cells have high AUC values for both gene sets!

Session Info

sessionInfo()
R version 4.4.1 (2024-06-14)
Platform: x86_64-pc-linux-gnu
Running under: Ubuntu 22.04.4 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/openblas-pthread/libblas.so.3 
LAPACK: /usr/lib/x86_64-linux-gnu/openblas-pthread/libopenblasp-r0.3.20.so;  LAPACK version 3.10.0

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

time zone: Etc/UTC
tzcode source: system (glibc)

attached base packages:
[1] stats4    stats     graphics  grDevices utils     datasets  methods  
[8] base     

other attached packages:
 [1] msigdbr_7.5.1               GSEABase_1.66.0            
 [3] graph_1.82.0                annotate_1.82.0            
 [5] XML_3.99-0.16.1             AnnotationDbi_1.66.0       
 [7] AUCell_1.26.0               SingleCellExperiment_1.26.0
 [9] SummarizedExperiment_1.34.0 Biobase_2.64.0             
[11] GenomicRanges_1.56.0        GenomeInfoDb_1.40.0        
[13] IRanges_2.38.0              S4Vectors_0.42.0           
[15] BiocGenerics_0.50.0         MatrixGenerics_1.16.0      
[17] matrixStats_1.3.0           optparse_1.7.5             

loaded via a namespace (and not attached):
  [1] jsonlite_1.8.8            magrittr_2.0.3           
  [3] ggbeeswarm_0.7.2          farver_2.1.1             
  [5] rmarkdown_2.26            fs_1.6.4                 
  [7] zlibbioc_1.50.0           vctrs_0.6.5              
  [9] memoise_2.0.1             DelayedMatrixStats_1.26.0
 [11] htmltools_0.5.8.1         S4Arrays_1.4.0           
 [13] BiocNeighbors_1.22.0      SparseArray_1.4.0        
 [15] sass_0.4.9                bslib_0.7.0              
 [17] htmlwidgets_1.6.4         plotly_4.10.4            
 [19] cachem_1.0.8              lifecycle_1.0.4          
 [21] pkgconfig_2.0.3           rsvd_1.0.5               
 [23] Matrix_1.7-0              R6_2.5.1                 
 [25] fastmap_1.1.1             GenomeInfoDbData_1.2.12  
 [27] digest_0.6.35             colorspace_2.1-0         
 [29] scater_1.32.0             irlba_2.3.5.1            
 [31] RSQLite_2.3.6             beachmat_2.20.0          
 [33] labeling_0.4.3            fansi_1.0.6              
 [35] httr_1.4.7                abind_1.4-5              
 [37] compiler_4.4.1            bit64_4.0.5              
 [39] withr_3.0.0               BiocParallel_1.38.0      
 [41] viridis_0.6.5             DBI_1.2.2                
 [43] highr_0.10                R.utils_2.12.3           
 [45] MASS_7.3-60.2             DelayedArray_0.30.0      
 [47] tools_4.4.1               vipor_0.4.7              
 [49] beeswarm_0.4.0            R.oo_1.26.0              
 [51] glue_1.7.0                nlme_3.1-164             
 [53] grid_4.4.1                generics_0.1.3           
 [55] gtable_0.3.5              tzdb_0.4.0               
 [57] R.methodsS3_1.8.2         tidyr_1.3.1              
 [59] data.table_1.15.4         hms_1.1.3                
 [61] BiocSingular_1.20.0       ScaledMatrix_1.12.0      
 [63] utf8_1.2.4                XVector_0.44.0           
 [65] ggrepel_0.9.5             pillar_1.9.0             
 [67] stringr_1.5.1             babelgene_22.9           
 [69] vroom_1.6.5               splines_4.4.1            
 [71] dplyr_1.1.4               getopt_1.20.4            
 [73] lattice_0.22-6            survival_3.5-8           
 [75] bit_4.0.5                 tidyselect_1.2.1         
 [77] Biostrings_2.72.0         scuttle_1.14.0           
 [79] knitr_1.46                gridExtra_2.3            
 [81] xfun_0.43                 mixtools_2.0.0           
 [83] stringi_1.8.3             UCSC.utils_1.0.0         
 [85] lazyeval_0.2.2            yaml_2.3.8               
 [87] evaluate_0.23             codetools_0.2-20         
 [89] kernlab_0.9-33            tibble_3.2.1             
 [91] cli_3.6.2                 xtable_1.8-4             
 [93] segmented_2.1-3           munsell_0.5.1            
 [95] jquerylib_0.1.4           Rcpp_1.0.12              
 [97] png_0.1-8                 parallel_4.4.1           
 [99] ggplot2_3.5.1             readr_2.1.5              
 [ reached getOption("max.print") -- omitted 9 entries ]
LS0tCnRpdGxlOiAiUGF0aHdheSBBbmFseXNpczogQVVDZWxsIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OiB0cnVlCmF1dGhvcjogQ0NETCBmb3IgQUxTRgpkYXRlOiAyMDI0Ci0tLQoKKkFkYXB0ZWQgZnJvbSBbdGhlIEFVQ2VsbCB2aWduZXR0ZV0oaHR0cHM6Ly9iaW9jb25kdWN0b3Iub3JnL3BhY2thZ2VzL3JlbGVhc2UvYmlvYy92aWduZXR0ZXMvQVVDZWxsL2luc3QvZG9jL0FVQ2VsbC5odG1sKSBhbmQgW3RoZSBgY2VsbC10eXBlLWV3aW5nc2AgbW9kdWxlXShodHRwczovL2dpdGh1Yi5jb20vQWxleHNMZW1vbmFkZS9PcGVuU2NQQ0EtYW5hbHlzaXMvdHJlZS9tYWluL2FuYWx5c2VzL2NlbGwtdHlwZS1ld2luZ3MpIHRoYXQgaXMgcGFydCBvZiB0aGUgT3BlbiBTaW5nbGUtY2VsbCBQZWRpYXRyaWMgQ2FuY2VyIEF0bGFzIHByb2plY3QuKgoKIyMgT2JqZWN0aXZlcwoKLSBJbnRyb2R1Y2UgdGhlIGBBVUNlbGxgIFIgcGFja2FnZQotIElsbHVzdHJhdGUgaG93IEFVQyB2YWx1ZXMgYXJlIGNhbGN1bGF0ZWQKLSBEZW1vbnN0cmF0ZSBob3cgQVVDIHZhbHVlcyBjYW4gYmUgdXNlZCBmb3IgY2VsbCBhc3NpZ25tZW50IGFuZCBwbG90dGluZwoKLS0tCgpJbiB0aGlzIG5vdGVib29rLCB3ZSdsbCBkZW1vbnN0cmF0ZSBob3cgdG8gdXNlIHRoZSBBVUNlbGwgbWV0aG9kLCBpbnRyb2R1Y2VkIGluIFtBaWJhciBfZXQgYWxfLiAyMDE3Ll0oaHR0cHM6Ly9kb2kub3JnLzEwLjEwMzgvbm1ldGguNDQ2MykuCgpXZSBjYW4gdXNlIEFVQ2VsbCB3aGVuIHdlIGFyZSBpbnRlcmVzdGVkIGluIGEgZ2VuZSBzZXQncyByZWxhdGl2ZSBleHByZXNzaW9uIG9yIGFjdGl2aXR5IGluIGFuIGluZGl2aWR1YWwgY2VsbC4KR2VuZSBzZXRzIGNhbiBjb21lIGZyb20gYSBjdXJhdGVkIGNvbGxlY3Rpb24gb2YgcHJpb3Iga25vd2xlZGdlLCBsaWtlIHRoZSBIYWxsbWFyayBjb2xsZWN0aW9uIHdlIHVzZWQgaW4gdGhlIGxhc3Qgbm90ZWJvb2ssIG9yIHdlIGNhbiB1c2Ugb3VyIG93biBjdXN0b20gZ2VuZSBzZXRzIChlLmcuLCBhIHNldCBvZiBtYXJrZXIgZ2VuZXMgZm9yIGEgY2VsbCB0eXBlIG9mIGludGVyZXN0KS4KCkEgbmljZSBmZWF0dXJlIG9mIEFVQ2VsbCBpcyB0aGF0IGl0IGlzIGJhc2VkIG9uIHJhbmtpbmcgZ2VuZXMgZnJvbSBoaWdoZXN0IHRvIGxvd2VzdCBleHByZXNzaW9uIHZhbHVlIGluIGFuIGluZGl2aWR1YWwgY2VsbCwgd2hpY2ggaXMgaGVscGZ1bCBpbiB0aGUgZm9sbG93aW5nIHdheXMgKFtBVUNlbGwgdmlnbmV0dGVdKGh0dHBzOi8vYmlvY29uZHVjdG9yLm9yZy9wYWNrYWdlcy9yZWxlYXNlL2Jpb2MvdmlnbmV0dGVzL0FVQ2VsbC9pbnN0L2RvYy9BVUNlbGwuaHRtbCkpOgoKLSBJdCBjYW4gdGFrZSBhIG51bWJlciBvZiBkaWZmZXJlbnQgdmFsdWVzIGFzIGlucHV0IChlLmcuLCByYXcgY291bnRzLCBUUE0pIAotIEl0IGNvbXBlbnNhdGVzIGZvciBkaWZmZXJlbmNlcyBpbiBsaWJyYXJ5IHNpemUsIHdoZXJlIHNvbWV0aGluZyBsaWtlIGF2ZXJhZ2luZyByYXcgY291bnQgdmFsdWVzIG9mIGdlbmVzIGluIGEgZ2VuZSBzZXQgd291bGQgbm90IAotIEl0IHNjYWxlcyB0byBsYXJnZXIgZGF0YXNldHMsIHNpbmNlIGNyZWF0aW5nIHJhbmtpbmdzIGlzIG5vdCBhcyByZXNvdXJjZS1pbnRlbnNpdmUgYXMgc29tZXRoaW5nIGxpa2UgcGVybXV0YXRpb24gdGVzdGluZywgYW5kIHdlIGNvdWxkIHNwbGl0IHVwIHRoZSBvYmplY3QgaW50byBzdWJzZXRzIG9mIGNlbGxzIGlmIG5lZWRlZAoKQVVDZWxsIGNhbGN1bGF0ZXMgdGhlIGFyZWEgdW5kZXIgdGhlIHJlY292ZXJ5IGN1cnZlIChBVUMpLCB3aGljaCAicmVwcmVzZW50cyB0aGUgcHJvcG9ydGlvbiBvZiBleHByZXNzZWQgZ2VuZXMgaW4gdGhlIHNpZ25hdHVyZSBhbmQgdGhlaXIgcmVsYXRpdmUgZXhwcmVzc2lvbiB2YWx1ZSBjb21wYXJlZCB0byB0aGUgb3RoZXIgZ2VuZXMgd2l0aGluIHRoZSBjZWxsIiAoW0FpYmFyIF9ldCBhbF8uIDIwMTcuXShodHRwczovL2RvaS5vcmcvMTAuMTAzOC9ubWV0aC40NDYzKSkuCldlIHdpbGwgdmlzdWFsaXplIHNvbWUgcmVjb3ZlcnkgY3VydmVzIGluIHRoZSBub3RlYm9vayB0byBnaXZlIHlvdSBhIGJldHRlciBpbnR1aXRpb24gYWJvdXQgdGhlIEFVQyBhbmQgaXRzIG1lYW5pbmcuCgpUaGUgQVVDIHZhbHVlcyB3ZSBnZXQgb3V0IG9mIEFVQ2VsbCBjYW4gYmUgdXNlZCBpbiBhIG51bWJlciBvZiB3YXlzIChbQWliYXIgX2V0IGFsXy4gMjAxNy5dKGh0dHBzOi8vZG9pLm9yZy8xMC4xMDM4L25tZXRoLjQ0NjMpKToKCi0gQXMgY29udGludW91cyB2YWx1ZXMgd2UgY2FuIHVzZSBmb3IgdmlzdWFsaXphdGlvbiBvciBjbHVzdGVyaW5nCi0gRm9yIGJpbmFyeSBhc3NpZ25tZW50IChpLmUuLCAib24iIGFuZCAib2ZmIiBvciAiZXhwcmVzc2VkIiBhbmQgIm5vdCBleHByZXNzZWQiKSBpZiB3ZSBwaWNrIGEgdGhyZXNob2xkIGVpdGhlciBhdXRvbWF0aWNhbGx5IHVzaW5nIGJ1aWx0LWluIGZ1bmN0aW9uYWxpdHkgb3IgbWFudWFsbHkgYnkgaW5zcGVjdGluZyB0aGUgZGlzdHJpYnV0aW9uIG9mIHNjb3JlcyBvdXJzZWx2ZXMKCldlIHdpbGwgdXNlIGFuIHNuUk5BLXNlcSBvZiBhIEV3aW5nIHNhcmNvbWEgc2FtcGxlIGZyb20gdGhlIFtgU0NQQ1AwMDAwMTVgIHByb2plY3RdKGh0dHBzOi8vc2NwY2EuYWxleHNsZW1vbmFkZS5vcmcvcHJvamVjdHMvU0NQQ1AwMDAwMTUpIG9uIHRoZSBTaW5nbGUtY2VsbCBQZWRpYXRyaWMgQ2FuY2VyIEF0bGFzIFBvcnRhbCBhbmQgdHdvIHJlbGV2YW50IGdlbmUgc2V0cyBmcm9tIHRoZSBNb2xlY3VsYXIgU2lnbmF0dXJlcyBEYXRhYmFzZSAoTVNpZ0RCKSB0byBkZW1vbnN0cmF0ZSB0aGlzIG1ldGhvZC4KCiMjIFNldCB1cAoKIyMjIExpYnJhcmllcwoKYGBge3IgbGlicmFyaWVzfQojIFdlIHdpbGwgYmUgbG9hZGluZyBhIFNpbmdsZUNlbGxFeHBlcmltZW50IG9iamVjdCBpbnRvIG91ciBlbnZpcm9ubWVudCBidXQgZG9uJ3QgbmVlZCB0byBzZWUgdGhlIHN0YXJ0dXAgbWVzc2FnZXMKc3VwcHJlc3NQYWNrYWdlU3RhcnR1cE1lc3NhZ2VzKHsKICBsaWJyYXJ5KFNpbmdsZUNlbGxFeHBlcmltZW50KQp9KQoKIyBMaWJyYXJ5IHdlJ2xsIHVzZSBmb3IgdGhlIGdlbmUgc2V0IGFuYWx5c2lzIGl0c2VsZgpsaWJyYXJ5KEFVQ2VsbCkKCiMgTGlicmFyaWVzIGZvciBhY2Nlc3NpbmcgYW5kIHdvcmtpbmcgd2l0aCBnZW5lIHNldHMKbGlicmFyeShHU0VBQmFzZSkKbGlicmFyeShtc2lnZGJyKQpgYGAKCiMjIyBEaXJlY3RvcmllcyBhbmQgZmlsZXMKCiMjIyMgRGlyZWN0b3JpZXMKCmBgYHtyIHNldHVwX2RpcmVjdG9yaWVzfQojIElucHV0IGRhdGEgCmV3aW5nX2RhdGFfZGlyIDwtIGZzOjpwYXRoKCJkYXRhIiwgImV3aW5nLXNhcmNvbWEiKQpwcm9jZXNzZWRfZGlyIDwtIGZzOjpwYXRoKGV3aW5nX2RhdGFfZGlyLCAicHJvY2Vzc2VkIikKCiMgRGlyZWN0b3J5IGZvciBob2xkaW5nIHBhdGh3YXkgYW5hbHlzaXMgcmVzdWx0cwphbmFseXNpc19kaXIgPC0gZnM6OnBhdGgoImFuYWx5c2lzIiwgImV3aW5nLXNhcmNvbWEiLCAicGF0aHdheS1hbmFseXNpcyIpCiMgQ3JlYXRlIGlmIGl0IGRvZXNuJ3QgZXhpc3QgeWV0CmZzOjpkaXJfY3JlYXRlKGFuYWx5c2lzX2RpcikKYGBgCgojIyMjIEZpbGVzCgpUaGUgaW5wdXQgd2lsbCBiZSBhIGBTaW5nbGVDZWxsRXhwZXJpbWVudGAgZm9yIGFuIGluZGl2aWR1YWwgRXdpbmcgc2FyY29tYSBsaWJyYXJ5LgoKYGBge3Igc2V0dXBfaW5wdXRfZmlsZXN9CnNjZV9maWxlIDwtIGZzOjpwYXRoKHByb2Nlc3NlZF9kaXIsIAogICAgICAgICAgICAgICAgICAgICAiU0NQQ1MwMDA0OTAiLCAKICAgICAgICAgICAgICAgICAgICAgIlNDUENMMDAwODIyX3Byb2Nlc3NlZC5yZHMiKQpgYGAKCldlIHdpbGwgc2F2ZSB0aGUgQVVDZWxsIHJlc3VsdHMgYXMgYSB0YWJsZSBpbiB0aGUgYW5hbHlzaXMgZGlyZWN0b3J5LgoKYGBge3Igc2V0dXBfb3V0cHV0X2ZpbGVzLCBsaXZlID0gVFJVRX0Kb3V0cHV0X2ZpbGUgPC0gZnM6OnBhdGgoYW5hbHlzaXNfZGlyLAogICAgICAgICAgICAgICAgICAgICAgICAiZXdpbmdfc2FyY29tYV9hdWNlbGxfcmVzdWx0cy50c3YiKQpgYGAKCgojIyMgRnVuY3Rpb25zCgpUaGUgYHNvdXJjZSgpYCBmdW5jdGlvbiBhbGxvd3MgdXMgdG8gbG9hZCBpbiBjdXN0b20gZnVuY3Rpb25zIHdlIHNhdmVkIGluIGFuIGAuUmAgZmlsZS4KCmBgYHtyIHNvdXJjZV9mdW5jdGlvbnN9CnNvdXJjZShmczo6cGF0aCgidXRpbCIsICJhdWNlbGxfZnVuY3Rpb25zLlIiKSkKYGBgCgpUaGlzIGxvYWRzIG9uZSBjdXN0b20gZnVuY3Rpb24sIGNhbGxlZCBgcGxvdF9yZWNvdmVyeV9jdXJ2ZSgpYCwgaW50byBvdXIgZW52aXJvbm1lbnQuClRoaXMgZnVuY3Rpb24gaXMgYWRhcHRlZCBmcm9tIFt0aGUgQVVDZWxsIHZpZ25ldHRlXShodHRwczovL2dpdGh1Yi5jb20vYWVydHNsYWIvQVVDZWxsL2Jsb2IvOTE3NTNiMzI3YTM5ZGM3YTRiYmVkNDY0MDhlYzIyNzFjNDg1ZjJmMC92aWduZXR0ZXMvQVVDZWxsLlJtZCNMMjk1LUwzMTYpLgoKIyMgU2V0IHVwIGdlbmUgc2V0cwoKV2UgYXJlIGdvaW5nIHRvIHVzZSB0d28gZ2VuZSBzZXRzIHBlcnRhaW5pbmcgdG8gRXdpbmcgc2FyY29tYS4KCiogW2BaSEFOR19UQVJHRVRTX09GX0VXU1IxX0ZMSTFfRlVTSU9OYF0oaHR0cHM6Ly93d3cuZ3NlYS1tc2lnZGIub3JnL2dzZWEvbXNpZ2RiL2dlbmVzZXRfcGFnZS5qc3A/Z2VuZVNldE5hbWU9WkhBTkdfVEFSR0VUU19PRl9FV1NSMV9GTEkxX0ZVU0lPTiksIHdoaWNoIGFyZSBnZW5lcyB0aGF0IHdlcmUgaGlnaGx5IGV4cHJlc3NlZCBpbiBhIHJoYWJkb215b3NhcmNvbWEgY2VsbCBsaW5lIGVuZ2luZWVyZWQgdG8gZXhwcmVzcyB0aGUgRVdTUjEtRkxJMSBmdXNpb24uCiogW2BSSUdHSV9FV0lOR19TQVJDT01BX1BST0dFTklUT1JfVVBgXShodHRwczovL3d3dy5nc2VhLW1zaWdkYi5vcmcvZ3NlYS9tc2lnZGIvY2FyZHMvUklHR0lfRVdJTkdfU0FSQ09NQV9QUk9HRU5JVE9SX1VQKSwgd2hpY2ggYXJlIGdlbmVzIHRoYXQgd2VyZSBoaWdobHkgZXhwcmVzc2VkIGluIG1lc2VuY2h5bWFsIHN0ZW0gY2VsbHMgZW5naW5lZXJlZCB0byBleHByZXNzIHRoZSBFV1MtRkxJMSBmdXNpb24gcHJvdGVpbi4KCldlIHdvdWxkIGV4cGVjdCBib3RoIG9mIHRoZXNlIGdlbmUgc2V0cyB0byBoYXZlIGhpZ2ggZXhwcmVzc2lvbiBpbiB0dW1vciBjZWxscy4KCmBgYHtyIGdlbmVzZXRzfQojIENyZWF0ZSBhIG5hbWVkIHZlY3RvciB3aXRoIHRoZSByZWxldmFudCBnZW5lIHNldCBuYW1lcwpld2luZ19nZW5lX3NldF9uYW1lcyA8LSBjKHpoYW5nID0gIlpIQU5HX1RBUkdFVFNfT0ZfRVdTUjFfRkxJMV9GVVNJT04iLAogICAgICAgICAgICAgICAgICAgICAgICAgIHJpZ2dpID0gIlJJR0dJX0VXSU5HX1NBUkNPTUFfUFJPR0VOSVRPUl9VUCIpCgpld2luZ19nZW5lX3NldF9uYW1lcwpgYGAKClRoZXNlIGdlbmUgc2V0cyBjb21lIGZyb20gdGhlIEMyIGdlbmUgc2V0IGNvbGxlY3Rpb24gZnJvbSBNU2lnREIuCkxldCdzIHJldHJpZXZlIHRoZW0gdXNpbmcgYG1zaWdkYnIoKWAuCgpgYGB7ciBleHRyYWN0X2dlbmVzZXRzLCBsaXZlID0gVFJVRX0KZXdpbmdfZ2VuZV9zZXRzX2RmIDwtIG1zaWdkYnIoc3BlY2llcyA9ICJIb21vIHNhcGllbnMiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjYXRlZ29yeSA9ICJDMiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN1YmNhdGVnb3J5ID0gIkNHUCIpIHw+CiAgZHBseXI6OmZpbHRlcihnc19uYW1lICVpbiUgZXdpbmdfZ2VuZV9zZXRfbmFtZXMpCmBgYAoKYEFVQ2VsbGAgdXNlcyBnZW5lIHNldHMgaW4gYSBwYXJ0aWN1bGFyIGZvcm1hdCB0aGF0IGNvbWVzIGZyb20gdGhlIGBHU0VBQmFzZWAgcGFja2FnZS4KV2UgbmVlZCB0byBjcmVhdGUgYSBgR2VuZVNldENvbGxlY3Rpb25gLgoKYGBge3IgZ2VuZV9zZXRfY29sbGVjdGlvbn0KZXdpbmdfZ2VuZV9zZXRfY29sbGVjdGlvbiA8LSBld2luZ19nZW5lX3NldF9uYW1lcyB8PgogIHB1cnJyOjptYXAoCiAgICAjIEZvciBlYWNoIGdlbmUgc2V0CiAgICBcKGdlbmVfc2V0X25hbWUpIHsKICAgICAgZXdpbmdfZ2VuZV9zZXRzX2RmIHw+CiAgICAgICAgIyBTdWJzZXQgdG8gdGhlIHJvd3MgaW4gdGhhdCBnZW5lIHNldAogICAgICAgIGRwbHlyOjpmaWx0ZXIoZ3NfbmFtZSA9PSBnZW5lX3NldF9uYW1lKSB8PgogICAgICAgICMgR3JhYiB0aGUgRW5zZW1ibCBnZW5lIGlkZW50aWZpZXJzCiAgICAgICAgZHBseXI6OnB1bGwoZW5zZW1ibF9nZW5lKSB8PgogICAgICAgICMgQ3JlYXRlIGEgR2VuZVNldCBvYmplY3QKICAgICAgICBHZW5lU2V0KHNldE5hbWUgPSBnZW5lX3NldF9uYW1lLAogICAgICAgICAgICAgICAgZ2VuZUlkVHlwZSA9IEVOU0VNQkxJZGVudGlmaWVyKCkpCiAgICB9CiAgKSB8PgogICMgVHVybiB0aGUgbGlzdCBvZiBHZW5lU2V0IG9iamVjdHMgaW50byBhIEdlbmVTZXQgY29sbGVjdGlvbgogIEdlbmVTZXRDb2xsZWN0aW9uKCkKYGBgCgojIyBSZWFkIGluIGFuZCBwcmVwYXJlIFNpbmdsZUNlbGxFeHBlcmltZW50CgpgYGB7ciByZWFkX2luX3NjZSwgbGl2ZSA9IFRSVUV9CnNjZSA8LSByZWFkcjo6cmVhZF9yZHMoc2NlX2ZpbGUpCmBgYAoKVGhlIGBBVUNlbGxgIGZ1bmN0aW9ucyB0YWtlcyBhbiBleHByZXNzaW9uIG1hdHJpeCB3aXRoIGdlbmVzIGFzIHJvd3MgYW5kIGNlbGxzIGFzIGNvbHVtbi4KV2UgY2FuIGV4dHJhY3QgYSBjb3VudHMgbWF0cml4IGluIHNwYXJzZSBmb3JtYXQgZm9yIHVzZSB3aXRoIGBBVUNlbGxgLgoKYGBge3IgY291bnRzX21hdHJpeH0KIyBFeHRyYWN0IGNvdW50cyBtYXRyaXgKY291bnRzX21hdHJpeCA8LSBjb3VudHMoc2NlKQpgYGAKClRoZXJlIG1heSBiZSBnZW5lcyBpbiBvdXIgZ2VuZSBzZXQgdGhhdCBkbyBub3QgYXBwZWFyIGluIHRoZSBTaW5nbGVDZWxsRXhwZXJpbWVudCBvYmplY3QuCldlIGNhbiByZW1vdmUgdGhlbSB1c2luZyB0aGUgYHN1YnNldEdlbmVTZXRzKClgIGZ1bmN0aW9uLgoKYGBge3Igc3Vic2V0X2dlbmVfc2V0cywgbGl2ZSA9IFRSVUV9CiMgUmVtb3ZlIGdlbmVzIGZyb20gZ2VuZSBzZXRzIGlmIHRoZXkgYXJlIG5vdCBpbiB0aGUgU0NFCmV3aW5nX2dlbmVfc2V0X2NvbGxlY3Rpb24gPC0gc3Vic2V0R2VuZVNldHMoZXdpbmdfZ2VuZV9zZXRfY29sbGVjdGlvbiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByb3duYW1lcyhjb3VudHNfbWF0cml4KSkKYGBgCgojIyBBVUNlbGwKCkFVQ2VsbCByZWxpZXMgb24gcmFua2luZyBnZW5lcyBmcm9tIGhpZ2hlc3QgdG8gbG93ZXN0IGV4cHJlc3Npb24gdmFsdWUgdG8gY2FsY3VsYXRlIHRoZSBBVUMuClRoZSBBVUMgaXMgdGhlIGFyZWEgdW5kZXIgdGhlIHJlY292ZXJ5IGN1cnZlLCB3aGljaCBjYXB0dXJlcyB0aGUgbnVtYmVyIG9mIGdlbmVzIGluIGEgZ2VuZSBzZXQgdGhhdCBhcmUgcHJlc2VudCBpbiB0aGUgcmFua2luZ3MgYWJvdmUgc29tZSB0aHJlc2hvbGQgKGkuZS4sIGl0IGlzIHRoZSBhcmVhIHVuZGVyIHRoZSBjdXJ2ZSB0byB0aGUgbGVmdCBvZiB0aGlzIGdlbmUgcmFuaykuCkJ5IGRlZmF1bHQsIHRoZSB0b3AgNSUgb2YgZ2VuZXMgYXJlIHVzZWQgYXMgdGhlIHRocmVzaG9sZC4KClNvbWUgZ2VuZXMgd2lsbCBub3QgYmUgZGV0ZWN0ZWQgKGkuZS4sIGhhdmUgMCBjb3VudHMpLgpHZW5lcyBjYW4gYWxzbyBoYXZlIHRoZSBzYW1lIGV4cHJlc3Npb24gbGV2ZWwgKGkuZS4sIHRpZXMpLgpUaGVzZSB1bmRldGVjdGVkIGdlbmVzIGFuZCB0aWVzIHdpbGwgYmUgcmFuZG9tbHkgb3JkZXJlZCBpbiBvdXIgcmFua2luZy4KVG8gbWFrZSBvdXIgcmFua2luZ3Mg4oCTIGFuZCB0aGVyZWZvcmUgcmVzdWx0cyDigJMgcmVwcm9kdWNpYmxlLCB3ZSB3aWxsIHNldCBhIHNlZWQuCgpgYGB7ciBzZXRfc2VlZCwgbGl2ZSA9IFRSVUV9CnNldC5zZWVkKDIwMjQpCmBgYAoKIyMjIENlbGwgcmFua2luZwoKVGhlIGZpcnN0IHN0ZXAgaW4gQVVDZWxsIGlzIHRvIHJhbmsgZ2VuZXMgZm9yIGVhY2ggY2VsbCBmcm9tIGhpZ2hlc3QgdG8gbG93ZXN0IGV4cHJlc3Npb24gdmFsdWUuCldlIGNhbiBkbyB0aGlzIHVzaW5nIHRoZSBgQVVDZWxsX2J1aWxkUmFua2luZ3MoKWAgZnVuY3Rpb24sIHdoaWNoIHdpbGwgb3V0cHV0IGEgdmlzdWFsaXphdGlvbiBzaG93aW5nIHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIG51bWJlciBvZiBnZW5lcyBkZXRlY3RlZCBpbiB0aGUgY2VsbHMgaW4gb3VyIFNpbmdsZUNlbGxFeHBlcmltZW50IG9iamVjdC4KCmBgYHtyIGNlbGxfcmFua2luZ3MsIGxpdmUgPSBUUlVFfQpjZWxsX3JhbmtpbmdzIDwtIEFVQ2VsbF9idWlsZFJhbmtpbmdzKGNvdW50c19tYXRyaXgpCmBgYAoKVGhlIEFVQ2VsbCBhdXRob3JzIHJlY29tbWVuZCBtYWtpbmcgc3VyZSBtb3N0IGNlbGxzIGhhdmUgYXQgbGVhc3QgdGhlIG51bWJlciBvZiBnZW5lcyB3ZSB3aWxsIHVzZSBhcyB0aGUgbWF4IHJhbmsgdG8gY2FsY3VsYXRlIHRoZSBBVUMuCgpUaGUgQVVDIG1heCByYW5rIHZhbHVlIHRlbGxzIEFVQ2VsbCB0aGUgY3V0b2ZmIGluIHRoZSBnZW5lIHJhbmtpbmdzIHRvIHVzZSBmb3IgY2FsY3VsYXRpbmcgQVVDOyB3ZSB3aWxsIHZpc3VhbGl6ZSB0aGlzIGN1cnZlIGFuZCBtYXggcmFuayBpbiBqdXN0IGEgbW9tZW50LgpJZiB3ZSBwaWNrZWQgYSBtYXggcmFuayBoaWdoZXIgdGhhbiB0aGUgbnVtYmVyIG9mIGdlbmVzIGRldGVjdGVkIGluIG1vc3QgY2VsbHMsIHRoZSBub24tZGV0ZWN0ZWQgZ2VuZXMgdGhhdCBhcmUgcmFuZG9tbHkgb3JkZXJlZCB3b3VsZCBwbGF5IGFuIG91dHNpemVkIHJvbGUgaW4gb3VyIEFVQyB2YWx1ZXMuCgpCeSBkZWZhdWx0LCB0aGUgbWF4IHJhbmsgaXMgdGhlIHRvcCA1JSBoaWdoZXN0IGV4cHJlc3NlZCBnZW5lcy4KV2UgY2FuIGNhbGN1bGF0ZSB0aGUgZGVmYXVsdCBtYXggcmFuayBieSB0YWtpbmcgaW50byBhY2NvdW50IHRoZSBudW1iZXIgb2YgZ2VuZXMuCgpgYGB7ciBleHBsb3JlX2F1Y19tYXhfcmFua30KbnJvdyhjZWxsX3JhbmtpbmdzKSAqIDAuMDUKYGBgCgpUaGlzIG51bWJlciBpcyBwcm9iYWJseSB0b28gaGlnaCwgZ2l2ZW4gdGhlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgbnVtYmVyIG9mIGdlbmVzIGRldGVjdGVkIGJ5IGNlbGwgd2UgdmlzdWFsaXplZCB3aXRoIGBBVUNlbGxfYnVpbGRSYW5raW5ncygpYC4KCldoYXQgaWYgd2UgY2hvc2UgYSAxJSB0aHJlc2hvbGQ/CgpgYGB7ciBsb3dlcl9tYXhfcmFuaywgbGl2ZSA9IFRSVUV9Cm5yb3coY2VsbF9yYW5raW5ncykgKiAwLjAxCmBgYAoKVGhhdCBpcyBwcm9iYWJseSBhIG1vcmUgcmVhc29uYWJsZSBjaG9pY2UgZm9yIHRoaXMgZGF0YXNldC4KCldlIGNhbiB1c2UgYSBmdW5jdGlvbiBjYWxsZWQgYGNlaWxpbmcoKWAgdG8gcm91bmQgdGhpcyBhbmQgc2F2ZSBpdCB0byBhIHZhcmlhYmxlIGZvciBsYXRlciB1c2UuCgpgYGB7ciBhdWNfbWF4X3JhbmssIGxpdmUgPSBUUlVFfQphdWNfbWF4X3JhbmsgPC0gY2VpbGluZyhucm93KGNlbGxfcmFua2luZ3MpICogMC4wMSkKYGBgCgojIyMgUGxvdHRpbmcgQVVDCgpUaGUgQVVDIHZhbHVlcyB3ZSBnZXQgb3V0IG9mIEFVQ2VsbCBhcmUgdGhlIGFyZWEgdW5kZXIgYSByZWNvdmVyeSBjdXJ2ZSBhbmQgZXN0aW1hdGUgdGhlIHByb3BvcnRpb24gb2YgZ2VuZXMgaW4gdGhlIGdlbmUgc2V0IHRoYXQgYXJlIGhpZ2hseSBleHByZXNzZWQgKGkuZS4sIGhpZ2hseSByYW5rZWQpLgoKTGV0J3MgcGxvdCB0aGUgcmVjb3ZlcnkgY3VydmUgZm9yIGEgY2VsbCB3aXRoIGhpZ2ggQVVDIGFuZCBhIGNlbGwgd2l0aCBsb3cgQVVDIHRvIGdldCBhIGJldHRlciBpbnR1aXRpb24gYWJvdXQgQVVDIHZhbHVlcy4KRWFybGllciwgd2UgbG9hZGVkIGEgY3VzdG9tIGZ1bmN0aW9uIHdlIGFkYXB0ZWQgZnJvbSBbdGhlIEFVQ2VsbCB2aWduZXR0ZV0oaHR0cHM6Ly9naXRodWIuY29tL2FlcnRzbGFiL0FVQ2VsbC9ibG9iLzkxNzUzYjMyN2EzOWRjN2E0YmJlZDQ2NDA4ZWMyMjcxYzQ4NWYyZjAvdmlnbmV0dGVzL0FVQ2VsbC5SbWQpIGNhbGxlZCBgcGxvdF9yZWNvdmVyeV9jdXJ2ZSgpYCB3aXRoIGBzb3VyY2UoKWAuCgpGaXJzdCwgd2UnbGwgc3RhcnQgd2l0aCBhIGNlbGwgd2l0aCBhIGhpZ2ggQVVDLgpXZSBwaWNrZWQgdGhpcyBiYXJjb2RlIGFoZWFkIG9mIHRpbWUgd2hlbiB3ZSB3cm90ZSB0aGUgbm90ZWJvb2suCgpgYGB7ciBoaWdoX3JlY292ZXJ5X2N1cnZlfQpwbG90X3JlY292ZXJ5X2N1cnZlKGNlbGxfcmFua2luZ3MsCiAgICAgICAgICAgICAgICAgICAgZXdpbmdfZ2VuZV9zZXRfY29sbGVjdGlvbiwKICAgICAgICAgICAgICAgICAgICBnZW5lX3NldF9uYW1lID0gIlpIQU5HX1RBUkdFVFNfT0ZfRVdTUjFfRkxJMV9GVVNJT04iLAogICAgICAgICAgICAgICAgICAgIGJhcmNvZGUgPSAiQ1RHQUdDR0dUQ1RUVEFUQyIsCiAgICAgICAgICAgICAgICAgICAgYXVjX21heF9yYW5rID0gYXVjX21heF9yYW5rKSAgIyAxJSB0aHJlc2hvbGQgCmBgYAoKVGhlIHgtYXhpcyBpcyB0aGUgZ2VuZSByYW5rcyBmb3IgYWxsIGdlbmVzLgpUaGUgeS1heGlzIGlzIHRoZSBudW1iZXIgb2YgZ2VuZXMgaW4gdGhlIHNpZ25hdHVyZSBhdCBhIGdpdmVuIHBvaW50IGluIHRoZSBnZW5lIHJhbmtpbmcg4oCTIHRoZSBsaW5lIHdpbGwgcmlzZSB3aGVuIGEgZ2VuZSBpbiB0aGUgZ2VuZSBzZXQgaXMgZW5jb3VudGVyZWQgaW4gdGhlIHJhbmtpbmcgZnJvbSBoaWdoZXN0IHRvIGxvd2VzdC4KVGhlIEFVQyBpcyB0aGUgYXJlYSB1bmRlciB0aGlzIHJlY292ZXJ5IGN1cnZlIGF0IHRoZSBtYXggcmFuayB0aHJlc2hvbGQgY2hvc2VuIGZvciB0aGlzIGRhdGFzZXQuCgpOb3csIGxldCdzIGxvb2sgYXQgYW4gZXhhbXBsZSB3aXRoIGEgbG93IEFVQy4KCmBgYHtyIGxvd19yZWNvdmVyeV9jdXJ2ZX0KcGxvdF9yZWNvdmVyeV9jdXJ2ZShjZWxsX3JhbmtpbmdzLAogICAgICAgICAgICAgICAgICAgIGV3aW5nX2dlbmVfc2V0X2NvbGxlY3Rpb24sCiAgICAgICAgICAgICAgICAgICAgZ2VuZV9zZXRfbmFtZSA9ICJaSEFOR19UQVJHRVRTX09GX0VXU1IxX0ZMSTFfRlVTSU9OIiwKICAgICAgICAgICAgICAgICAgICBiYXJjb2RlID0gIkFHQVRBR0FHVENBQ0FBVEMiLAogICAgICAgICAgICAgICAgICAgIGF1Y19tYXhfcmFuayA9IGF1Y19tYXhfcmFuaykgICMgMSUgdGhyZXNob2xkCmBgYAoKRmFyIGZld2VyIGdlbmVzIGluIHRoZSBnZW5lIHNldCBhcmUgcmFua2VkIGFib3ZlIHRoZSB0aHJlc2hvbGQsIHlpZWxkaW5nIGEgbG93ZXIgQVVDIHZhbHVlLgoKIyMjIENhbGN1bGF0aW5nIHRoZSBBVUMKCk9uY2Ugd2UgaGF2ZSB0aGUgcmFua2luZ3MsIHdlIGNhbiBjYWxjdWxhdGUgdGhlIEFVQyBzY29yZXMgZm9yIGJvdGggZ2VuZSBzZXRzIGluIGFsbCBjZWxscyB3aXRoIHRoZSBgQVVDZWxsX2NhbGNBVUMoKWAgZnVuY3Rpb24uCgpgYGB7ciBjYWxjX2F1YywgbGl2ZSA9IFRSVUV9CmNlbGxfYXVjIDwtIEFVQ2VsbF9jYWxjQVVDKGdlbmVTZXRzID0gZXdpbmdfZ2VuZV9zZXRfY29sbGVjdGlvbiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHJhbmtpbmdzID0gY2VsbF9yYW5raW5ncywKICAgICAgICAgICAgICAgICAgICAgICAgICAgYXVjTWF4UmFuayA9IGF1Y19tYXhfcmFuaykKYGBgCgpUaGlzIGZ1bmN0aW9uIHJldHVybnMgYW4gYGF1Y2VsbFJlc3VsdHNgIG9iamVjdC4KCmBgYHtyIGNoZWNrX3N0ciwgbGl2ZSA9IFRSVUV9CnN0cihjZWxsX2F1YykKYGBgCgpJdCBjYW4gYmUgbXVjaCBtb3JlIGNvbnZlbmllbnQgdG8gd29yayB3aXRoIHRoaXMgaW4gYSB0YWJ1bGFyIGZvcm1hdC4KCmBgYHtyIGF1Y190b190YWJsZX0KIyBFeHRyYWN0IEFVQwphdWNfZGYgPC0gY2VsbF9hdWNAYXNzYXlzQGRhdGEkQVVDIHw+CiAgIyBUcmFuc3Bvc2UKICB0KCkgfD4KICAjIENvbnZlcnQgdG8gZGF0YSBmcmFtZQogIGFzLmRhdGEuZnJhbWUoKSB8PgogICMgTWFrZSB0aGUgYmFyY29kZXMgYSBjb2x1bW4KICB0aWJibGU6OnJvd25hbWVzX3RvX2NvbHVtbigiYmFyY29kZXMiKSAKCiMgTG9vayBhdCBmaXJzdCBmZXcgcm93cwpoZWFkKGF1Y19kZikKYGBgCgojIyMgQXNzaWdubWVudHMKCkFVQ2VsbCBjYW4gYXNzaWduIGNlbGxzIGFzIGhhdmluZyBhbiBhY3RpdmUgZ2VuZSBzZXQgb3Igbm90IGJ5IHBpY2tpbmcgYSB0aHJlc2hvbGQgYXV0b21hdGljYWxseS4KV2UnbGwgZXhwbG9yZSB0aGVzZSBpbiBhIGxhdGVyIHBsb3QsIGJ1dCBmb3Igbm93LCBsZXQncyBjYWxjdWxhdGUgdGhlIHRocmVzaG9sZCBhbmQgYXNzaWduIGNlbGxzIHdpdGggYEFVQ2VsbF9leHBsb3JlVGhyZXNob2xkcygpYC4KCmBgYHtyIGF1Y19hc3NpZ25tZW50cywgbGl2ZSA9IFRSVUV9CmF1Y19hc3NpZ25tZW50cyA8LSBBVUNlbGxfZXhwbG9yZVRocmVzaG9sZHMoY2VsbF9hdWMsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBsb3RIaXN0ID0gRkFMU0UsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFzc2lnbkNlbGxzID0gVFJVRSkKYGBgCgpXZSdyZSBnb2luZyB0byBwbG90IHRoZSBkaXN0cmlidXRpb24gb2YgQVVDIHZhbHVlcyB3aXRoIGBnZ3Bsb3QyYCwgc28gd2Ugd2lsbCB3YW50IHRoZSBBVUMgdmFsdWVzIGluIGEgbG9uZ2VyIGZvcm1hdC4KCmBgYHtyIGF1Y19wbG90dGluZ19kZn0KYXVjX3Bsb3R0aW5nX2RmIDwtIGF1Y19kZiB8PgogIHRpZHlyOjpwaXZvdF9sb25nZXIoIWJhcmNvZGVzLAogICAgICAgICAgICAgICAgICAgICAgbmFtZXNfdG8gPSAiZ2VuZV9zZXQiLAogICAgICAgICAgICAgICAgICAgICAgdmFsdWVzX3RvID0gImF1YyIpIHw+CiAgZHBseXI6Om11dGF0ZSgKICAgICMgQ3JlYXRlIGEgbmV3IGxvZ2ljYWwgY29sdW1uIGNhbGxlZCBhc3NpZ25lZAogICAgYXNzaWduZWQgPSBkcGx5cjo6Y2FzZV93aGVuKAogICAgICAjIEZvciBaaGFuZyBnZW5lIHNldCByb3dzLCBzZXQgdG8gVFJVRSB3aGVuIHRoZSBiYXJjb2RlIGlzIGluIHRoZSAKICAgICAgIyBhc3NpZ25tZW50IGxpc3QKICAgICAgZ2VuZV9zZXQgPT0gZXdpbmdfZ2VuZV9zZXRfbmFtZXNbWyJ6aGFuZyJdXSAmIAogICAgICAgIGJhcmNvZGVzICVpbiUgYXVjX2Fzc2lnbm1lbnRzW1tld2luZ19nZW5lX3NldF9uYW1lc1tbInpoYW5nIl1dXV0kYXNzaWdubWVudCB+IFRSVUUsCiAgICAgICMgRm9yIFJpZ2dpIGdlbmUgc2V0IHJvd3MsIHNldCB0byBUUlVFIHdoZW4gdGhlIGJhcmNvZGUgaXMgaW4gdGhlIAogICAgICAjIGFzc2lnbm1lbnQgbGlzdAogICAgICBnZW5lX3NldCA9PSBld2luZ19nZW5lX3NldF9uYW1lc1tbInJpZ2dpIl1dICYgCiAgICAgICAgYmFyY29kZXMgJWluJSBhdWNfYXNzaWdubWVudHNbW2V3aW5nX2dlbmVfc2V0X25hbWVzW1sicmlnZ2kiXV1dXSRhc3NpZ25tZW50IH4gVFJVRSwKICAgICAgIyBPdGhlcndpc2UsIHNldCB0byBGQUxTRQogICAgICAuZGVmYXVsdCA9IEZBTFNFCiAgICApCiAgKQoKYXVjX3Bsb3R0aW5nX2RmCmBgYAoKVG8gZHJhdyB2ZXJ0aWNhbCBsaW5lcyByZXByZXNlbnRpbmcgdGhlIGF1dG9tYXRpY2FsbHkgY2hvc2VuIHRocmVzaG9sZCwgd2UgY2FuIGNyZWF0ZSBhIHNlcGFyYXRlIGRhdGEgZnJhbWUuCgpgYGB7ciBhdWNfdGhyZXNob2xkX2RmfQphdWNfdGhyZXNob2xkX2RmIDwtIGRhdGEuZnJhbWUoCiAgZ2VuZV9zZXQgPSBld2luZ19nZW5lX3NldF9uYW1lcywKICAjIEdyYWIgdGhyZXNob2xkcyBhc3NvY2lhdGVkIHdpdGggZWFjaCBnZW5lIHNldCBmcm9tIGFzc2lnbmVtZW50cyBvYmplY3QKICB0aHJlc2hvbGQgPSBjKGF1Y19hc3NpZ25tZW50c1tbZXdpbmdfZ2VuZV9zZXRfbmFtZXNbInpoYW5nIl1dXSRhdWNUaHIkc2VsZWN0ZWQsIAogICAgICAgICAgICAgICAgYXVjX2Fzc2lnbm1lbnRzW1tld2luZ19nZW5lX3NldF9uYW1lc1sicmlnZ2kiXV1dJGF1Y1RociRzZWxlY3RlZCkKKQoKYXVjX3RocmVzaG9sZF9kZgpgYGAKCk5vdyBsZXQncyBtYWtlIGEgZGVuc2l0eSBwbG90LCBwbG90dGluZyB0aGUgZGVuc2l0eSBvZiB0aGUgYXNzaWduZWQgYW5kIHVuYXNzaWduZWQgY2VsbHMgc2VwYXJhdGVseSBhbmQgZHJhd2luZyBhIHZlcnRpY2FsIGxpbmUgZm9yIHRoZSB0aHJlc2hvbGQuCgpgYGB7ciBhdWNfZGVuc2l0eV9wbG90fQphdWNfcGxvdHRpbmdfZGYgfD4KICBnZ3Bsb3QyOjpnZ3Bsb3QoCiAgICBnZ3Bsb3QyOjphZXMoCiAgICAgIHggPSBhdWMsICAjIEFVQyB2YWx1ZXMKICAgICAgY29sb3IgPSBhc3NpZ25lZCwgICMgR3JvdXAgYnkgYXNzaWdubWVudAogICAgICBmaWxsID0gYXNzaWduZWQsICAgIyBHcm91cCBieSBhc3NpZ25tZW50CiAgICApCiAgKSArCiAgZ2dwbG90Mjo6Z2VvbV9kZW5zaXR5KGFscGhhID0gMC4yKSArCiAgIyBEcmF3IGEgdmVydGljYWwgZG90dGVkIGxpbmUgc2hvd2luZyB0aGUgdGhyZXNob2xkIGZvciBlYWNoIGdlbmUgc2V0CiAgZ2dwbG90Mjo6Z2VvbV92bGluZShkYXRhID0gYXVjX3RocmVzaG9sZF9kZiwKICAgICAgICAgICAgICAgICAgICAgIG1hcHBpbmcgPSBnZ3Bsb3QyOjphZXMoeGludGVyY2VwdCA9IHRocmVzaG9sZCksCiAgICAgICAgICAgICAgICAgICAgICBsdHkgPSAyKSArCiAgIyBQbG90IGVhY2ggZ2VuZSBzZXQgaW4gaXRzIG93biBmYWNldAogIGdncGxvdDI6OmZhY2V0X2dyaWQoY29scyA9IGdncGxvdDI6OnZhcnMoZ2VuZV9zZXQpKSArCiAgIyBVc2UgYSBidWlsdC1pbiB0aGVtZQogIGdncGxvdDI6OnRoZW1lX2J3KCkKYGBgCgpGb3IgdGhlc2UgcGFydGljdWxhciBnZW5lIHNldHMsIHRoZSBBVUMgdmFsdWVzIGFwcGVhciB0byBiZSBiaW1vZGFsbHkgZGlzdHJpYnV0ZWQsIGFuZCB3ZSBjYW4gZWFzaWx5IGlkZW50aWZ5IGNlbGxzIHdoZXJlIHRoZSBnZW5lcyBhcmUgaGlnaGx5IGV4cHJlc3NlZC4KCkxldCdzIHdyaXRlIHRoaXMgdGFibGUgdG8gdGhlIG91dHB1dCBmaWxlLgoKYGBge3Igc2F2ZV9hdWN9CmF1Y19wbG90dGluZ19kZiB8PiAKICByZWFkcjo6d3JpdGVfdHN2KG91dHB1dF9maWxlKQpgYGAKCiMjIyBVTUFQcwoKIyMjIyBBZGRpbmcgQVVDIHRvIGBjb2xEYXRhYAoKV2UgY2FuIGFsc28gYWRkIHRoZSBBVUMgdmFsdWVzIGJhY2sgaW50byB0aGUgU2luZ2xlQ2VsbEV4cGVyaW1lbnQgZm9yIGNvbnZlbmllbmNlLCBlLmcuLCBmb3IgcGxvdHRpbmcuCldlJ2xsIGFkZCBpdCB0byB0aGUgZXhpc3RpbmcgYGNvbERhdGFgLgoKRmlyc3QsIGxldCdzIHJlbmFtZSB0aGUgZ2VuZSBzZXQgY29sdW1ucyB0byBzb21ldGhpbmcgbW9yZSBlYXNpbHkgdHlwZWQuCgpgYGB7ciByZW5hbWVfZ2VuZV9zZXR9CmF1Y19kZiA8LSBhdWNfZGYgfD4KICAjIFVzZSBzaG9ydGVyIG5hbWVzCiAgZHBseXI6OnJlbmFtZSh6aGFuZ19hdWMgPSBld2luZ19nZW5lX3NldF9uYW1lc1tbInpoYW5nIl1dLAogICAgICAgICAgICAgICAgcmlnZ2lfYXVjID0gZXdpbmdfZ2VuZV9zZXRfbmFtZXNbWyJyaWdnaSJdXSkKCmBgYAoKQW5kIGpvaW4gaXQgdG8gdGhlIGV4aXN0aW5nIGBjb2xEYXRhYC4KCmBgYHtyIGNvbGRhdGEsIGxpdmUgPSBUUlVFfQojIEV4dHJhY3QgdGhlIGV4aXN0aW5nIGNvbERhdGEsIGFuZCBsZWZ0IGpvaW4gaXQgd2l0aCB0aGUgQVVDIHZhbHVlcyBieSB0aGUKIyBiYXJjb2Rlcwpjb2xkYXRhX2RmIDwtIGNvbERhdGEoc2NlKSB8PgogIGFzLmRhdGEuZnJhbWUoKSB8PgogIGRwbHlyOjpsZWZ0X2pvaW4oCiAgICBhdWNfZGYsCiAgICBieSA9ICJiYXJjb2RlcyIKICApCmBgYAoKTm93LCB3ZSdyZSByZWFkeSB0byBhZGQgaXQgYmFjayB0byB0aGUgb2JqZWN0LgoKYGBge3IgYWRkX2JhY2tfY29sRGF0YSwgbGl2ZSA9IFRSVUV9CiMgV2UgbmVlZCB0byBzYXZlIHRoaXMgYXMgYSBEYXRhRnJhbWUKY29sRGF0YShzY2UpIDwtIERhdGFGcmFtZSgKICBjb2xkYXRhX2RmLAogIHJvdy5uYW1lcyA9IGNvbERhdGEoc2NlKSRiYXJjb2RlcwopCmBgYAoKIyMjIyBQbG90dGluZyBVTUFQcwoKV2UgY2FuIHVzZSB0aGUgYHBsb3RVTUFQKClgIGZ1bmN0aW9uIGZyb20gdGhlIGBzY2F0ZXJgIHBhY2thZ2UgdG8gcGxvdCBhIFVNQVAgd2l0aCB0aGUgcG9pbnRzIGNvbG9yZWQgYnkgdGhlIEFVQyB2YWx1ZQoKYGBge3IgcGxvdF91bWFwX3poYW5nfQpzY2F0ZXI6OnBsb3RVTUFQKHNjZSwgY29sb3VyX2J5ID0gInpoYW5nX2F1YyIpICsKICAjIFVzZSB0aGUgZ2VuZSBzZXQgbmFtZSwgcmVwbGFjaW5nIHVuZGVyc2NvcmVzIHdpdGggc3BhY2VzCiAgZ2dwbG90Mjo6Z2d0aXRsZShzdHJpbmdyOjpzdHJfcmVwbGFjZV9hbGwoZXdpbmdfZ2VuZV9zZXRfbmFtZXNbWyJ6aGFuZyJdXSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIlxcXyIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICIgIikpCmBgYAoKTGV0J3MgY29sb3IgdGhlIHBvaW50cyBieSB0aGUgQVVDIHZhbHVlcyBmb3IgdGhlIG90aGVyIGdlbmUgc2V0LgoKYGBge3IgcGxvdF91bWFwX3JpZ2dpLCBsaXZlID0gVFJVRX0Kc2NhdGVyOjpwbG90VU1BUChzY2UsIGNvbG91cl9ieSA9ICJyaWdnaV9hdWMiKSArIAogIGdncGxvdDI6OmdndGl0bGUoc3RyaW5ncjo6c3RyX3JlcGxhY2VfYWxsKGV3aW5nX2dlbmVfc2V0X25hbWVzW1sicmlnZ2kiXV0sIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJcXF8iLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiICIpKQpgYGAKCldlIHdvdWxkIHdhbnQgdG8gZG8gc29tZXRoaW5nIG1vcmUgZm9ybWFsIHRvIGNvbmZpcm0sIGJ1dCBpdCBzZWVtcyBsaWtlIHRoZSBzYW1lIGNlbGxzIGhhdmUgaGlnaCBBVUMgdmFsdWVzIGZvciBib3RoIGdlbmUgc2V0cyEKCiMjIFNlc3Npb24gSW5mbwoKYGBge3Igc2Vzc2lvbl9pbmZvfQpzZXNzaW9uSW5mbygpCmBgYAo=